×

# STD - EDITORIAL

 0 PRACTICE CONTEST 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[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]); } } This question is marked "community wiki". asked 03 Apr '16, 00:12 16●3 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,723
×36
×13

question asked: 03 Apr '16, 00:12

question was seen: 965 times

last updated: 16 May '16, 14:15