You are not logged in. Please login at www.codechef.com to post your questions!

×

STD - EDITORIAL

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.

  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]);

}

}

This question is marked "community wiki".

asked 03 Apr '16, 00:12

ma14ab03_1995's gravatar image

2★ma14ab03_1995
163
accept rate: 0%

edited 16 May '16, 14:15

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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