Author- Medha Pandey

Tester- Akanksha Bigasia

Editorialist- Akanksha Bigasia

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*<=sqrt(n);i++)
{
if(n%primes*==0)
{
c++;//count the distinct prime factors.
while(n%primes*==0)
{
n/=primes*;
}
}
}
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]);

```
}
```

}