[PRACTICE][1]
[CONTEST][2]
Author- [Medha Pandey][3]
Tester- [Akanksha Bigasia][4]
Editorialist- [Akanksha Bigasia][5]
DIFFICULTY:
Easy-medium
PREREQUISITES:
Maths and number theory
PROBLEM:
The problem is asking for first 1000 numbers having distinct prime divisors greater than equal to 3.
EXPLANATION:
There are several methods to find distinct prime division.
-
using sieve
-
by trial division.
Here is the simple solution using trial divisor to find the distinct prime factors, discussed after short explanation.
This task can be done using a simple implementation . Just find all the primes, for numbers by multiplying 3 primes and then for each numbed found , multiply it again with the same primes we used from the beginning, and then when we got a list, we can sort it and we are ready to read the input and output the answer right away. But first for doing this we need to make sure that for n=1000 the number needed won’t be too great.
The primes are 2,3,5,7,11,13,17,19,23,29,31,37,41 Our initial numbers are going to be made by multiplying 3 different primes. It is not hard to notice that the 1000th number is not going to be formed with a greater number than 41. So we can be sure that a simple brute force solution will pass the time limit easily.
#include < cstdio >
#include < cmath >
int primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
int lucky[1001];
int factor(int n)
{
int c=0;
for(int i=0;primes[i]<=sqrt(n);i++)
{
if(n%primes[i]==0)
{
c++;//count the distinct prime factors.
while(n%primes[i]==0)
{
n/=primes[i];
}
}
}
if(n > 1)c++;
return c;
}
void calc()
{ int k=1;
for(int n=30;n<2665;n++)
{
if(factor(n)>=3)
{
lucky[k++]=n;//if number have 3 or mote distinct prime factors store it in array.
}
}
}
int main(void)
{
int tc,i,j;
int n,sum=0;
calc();
scanf("%d",&tc);
while(tc--)
{
scanf("%d",&n);
printf("%d",lucky[n]);
}
}
[1]: https://www.codechef.com/problems/STD
[2]: https://www.codechef.com/IC32016
[3]: https://www.codechef.com/users/mack8
[4]: https://www.codechef.com/users/akku_bigasia
[5]: https://www.codechef.com/users/akku_bigasia