STD - EDITORIAL

[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.

  1. using sieve

  2. 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