numbers which have atleast one prime digit less than or equal to n.

editorial
, , , ,
1

Little Aaryan loves going to the magic shows, One fine day after attending a magic show, he thought randomly of some numbers, He introduced some magic in them, The magic was each number had atleast one prime digit in it. He called those numbers as magical numbers. Too excited next day, he went to the magic show and asked the performer to answer his following query

Given a number N, you have to find the number of magical numbers less than or equal to N.

T <= 10^6

N <= 10^18

Time Limit - 2 Sec .

Can any one help me how to solve this ?

2

#include
using namespace std;
#include<conio.h>
#include<stdio.h>

int main()
{
int i,j,l,n,k,prime_number=0,magic_number=0;

 cout<<"Enter the number: ";	
 cin>>n;
 
 for( i=2;i<=n ;i++)
 {
 	k = i;
 	int z=k;
 	while(k>0)
 	{
 		l = k%10;
 		for( j =1 ; j<=l ;j++)
 		{
 			if(l%j ==0)
 			prime_number++;
 		}
 		if(prime_number == 2)
 		{
 		magic_number++;
 		prime_number = 0;
 		cout<<z<<"\n";
 		break;
 		}
 		prime_number = 0;
 		k /=10;
 		
 	}
 }
 //cout<<"Number of prime number = "<<magic_number;
 return 0;

}

just remove last comment // to see total number having at least one prime digit in it; cout statement in if condition, print those number that have at least one prime digit in it;

3

#include<stdio.h>
void main()
{
long count=0,input,i,temp=0;
int k;
printf(“enter a no: “);
scanf(”%d”,&input);
for(i=1;i<=input;i++)
{
temp=i;
while(temp!=0)
{
k=temp%10;
if(k==2 ||k== 3 ||k== 5||k==7 )
{
count++;
// printf("%d\n",i);
break;
}
temp=temp-k;
temp=temp/10;
}

}

printf("%d",count);
}

1 Like
4

thx for your reply. but time limit is 2 sec . how to solve this in 2 sec.

1<= n <= 10^18

5

anilgr, you don’t need “temp=temp-k;” in your code. “temp=temp/10;” would be sufficient.
long an integer value.

6

I think this can be done by using combinatorics:

There are only 4 1-digit magical nos. i.e. {2,3,5,7}

No. of 2-digit magical nos. can be computed by choosing 2 numbers, one from each of the following 2 sets {2,3,5,7} and {0,1,4,6,8,9} = 4C1 X 6C1 + 5C1 X 4C1 + 4C2 X 2 + 4= 60.We add 4 becoz of the numbers having 2 repeated prime digits i.e. {22,33,55,77}

We can compute in this way for 3,4,5 digit numbers.This is just a hint.

7

You can easily digit DP over this

8

Any place where we can submit code ?

9

provide link for this question to submit answer???