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

×

PRETNUM - Editorial

4
5

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY

PREREQUISITES:

Prime factorization, Sieve

PROBLEM:

Find the number of integers in the given range which have prime number of divisors.

QUICK EXPLANATION:

Although L and R can be as high as 10^12 but R-L is <= 10^6, this allows us to iterate through the complete range and count the number of divisors of each number in the range.

EXPLANATION:

Approach 1:
If a number N is divisible by D then either it has 2 factors(D and N/D) or it is square of D. Another thing to note is that if a number has 2 divisors x and y such that x < y, then x < sqrt(N) and y > sqrt(N). Using these 2 facts we can iterate through all the numbers in range [1, sqrt(R)] and count the number of factors for each of the number.

Working commented solution follows:

bool isPrime[10000]; void init() { // Since range is very small so not used Sieve for (int i = 2; i < sizeof(isPrime); ++i) { int j = 2; for (; j * j <= i; ++j) { if (i % j == 0) { break; } } if (j * j > i) isPrime[i] = true; } }

main() { init(); int testCases, divisors[1000005]; scanf("%d", &testCases); while(testCases--) { long long L, R; scanf("%lld%lld", &L, &R); for(long long i=L; i<=R; i++) divisors[i-L] = 0; //Initialize divisors of all numbers to 0 for(long long i=1; i*i <= R; i++) { // Iterate through 1 to sqrt(R) long long square = i*i; // j starts with first number in range [L, R] which is multiple of i for(long long j=( (L-1) / i + 1) * i; j <= R; j += i) { // Factors under consideration are i and j / i if (j < square) continue; // Already counted because of 2 in else condition below if( square == j ) // Just 1 factor divisors[j-L] += 1; else divisors[j-L] += 2; // Counting factors i and j / i } } int ans = 0; for(long long i = L; i <= R; i++) if(isPrime[divisors[i-L]]) ans++; printf("%d\n",ans); } }

Approach 2:
This approach is taken by more coders including tester. This is based on prime factorization of a number and then counting the total number of divisors.

Lets take an example:
Consider prime factors breakdown of 18 (2^1 * 3^2) so total number of factors are (1+1) * (2 + 1) = 6 [Factors: 1, 2, 3, 6, 9, 18]. Similarly if a number is p1^x1 * p2^x2 * p3^x3 * … then total number of factors is (x1+1) * (x2+1) * (x3+1) * …

Now if we generate all primes <= 10^6 using sieve and later use them to find out how many times it goes into each number in the given range, we know the number of divisors composed of primes <= 10^6. We may have missed 1 prime number > 10^6 which might have fallen in the range as range goes as high as 10^12. But we are sure that there is only 1 such prime! So if we detect this case we can simply multiply our number of factors calculated so far by (1+1). See tester’s solution for working code.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be uploaded soon
Tester's solution can be found here and here

asked 11 Nov '13, 23:05

shaleen's gravatar image

4★shaleen ♦♦
616913
accept rate: 0%


10

We don't need to count factors of each numbers, only for perfect squares in the range, am i right?

Because apart from primes (2 factors), only perfect squares can have prime number of factors since only perfect squares have odd number of factors, other numbers have even number of factors(except 2 no of factors)

So we can calculate number of factors of only perfect squares and look that up to be prime between [1,200]

link

answered 11 Nov '13, 23:25

yashkumar18's gravatar image

6★yashkumar18
82761224
accept rate: 18%

edited 12 Nov '13, 23:38

All we need to do is to count the no of numbers that are powers of prime such that power+1 is also prime!! ;-)

link

answered 12 Nov '13, 01:12

chandan721's gravatar image

3★chandan721
2013919
accept rate: 0%

the numbers follow a pattern... p^(q-1) where both p and q are prime .. i used sieve to figure out all the prime numbers.. and simple math to figure out how many numbers are powers of (prime-1) that comes within the given range of 'l' to 'r' .. worked out well n good !!
http://www.codechef.com/viewsolution/2976601

link

answered 12 Nov '13, 01:56

mecodesta's gravatar image

4★mecodesta
364151827
accept rate: 0%

edited 14 Nov '13, 10:36

Is this what you did? 2,3,5,7,11,...............,999999999989 squares of 2,3,5,7,.......,999983 power 4 of 2,3,5,7,.......,997 power 6 of 2,3,5,7,.......,97 power 10 of 2,3,5,7,11,13 power 12 of 2,3,5,7 power 16 of 2,3,5 power 18 of 2,3 power 22 of 2,3 power 28 of 2 power 30 of 2 and power 36 of 2 This is the pattern i could guess when i was working on this question. But then i got stuck because of the space constraint in C++. It can count the rest. The problem is only with the prime numbers after 10^6. Can you help me with this?

(04 Dec '13, 23:50) whizcode2★

@whizcode, sorry i couldn't get to you soon .. was occupied with december challenge.! And no that wasn't what i did, i just calculated all the prime numbers in that interval using seive and then used dp to calculate powers of (prime-1) in that interval, thats all the problem requires :)

(10 Dec '13, 03:38) mecodesta4★

Hi Admin,

Could you please tell me ans for 1000000 1000100 I have checked with some solutions those are giving answer as 6 but here is one accepted solution that is giving ans 5 http://www.codechef.com/viewplaintext/2977722

as we can see ans should be 6 [1000003,1000033,1000037,1000039,1000081,1000099]

Thanks,

link

answered 12 Nov '13, 23:00

y07uc118's gravatar image

3★y07uc118
311
accept rate: 0%

Find all perfect squares and prime numbers in the range [l,r].

Check if square root of a perfect square has exactly one prime divisor( is of the form prime^(k) ), because product of two numbers can never be prime.

Then original number is prime^(2k) Number of divisors of prime^(2k) = 2k+1.

Then using sieve check if 2k+1 is prime. If prime add 1 to answer.

Also add number of prime numbers between [l,r] to the answer. my solution

link

answered 17 Jun '16, 21:12

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

CAN ANYONE TELL WHATS WRONG WITH MY CODE http://www.codechef.com/viewsolution/2975377

link

answered 12 Nov '13, 20:26

harshitggrwl's gravatar image

2★harshitggrwl
1
accept rate: 0%

Run time error for large inputs
http://ideone.com/qkLWfU
Declaring array every time: primes= new (nothrow) uint64[r];
Declare it global..

(12 Nov '13, 21:36) abhinav_nitrr1★

@shaleen

I didn't get the part where you say "We may have missed 1 prime number > 10^6 which might have fallen in the range as range goes as high as 10^12. But we are sure that there is only 1 such prime! So if we detect this case we can simply multiply our number of factors calculated so far by (1+1) .

Also I think it should be the ((prime > 10^6) + 1) in the end,right ?

link

answered 08 Jun '16, 14:46

avinish's gravatar image

2★avinish
0111
accept rate: 0%

Any number from the range [1,10^12]. Will have following properties:

  1. Can either be a prime number
  2. Or will have atleast one prime number from range [1,10^6] in its prime factorisation.
  3. And it can not be product of two primes both >10^6.

It helped me in finding all primes in the range [l,r]

link

answered 17 Jun '16, 21:50

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

edited 17 Jun '16, 21:53

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:

×11,590
×2,610
×206
×31
×15

question asked: 11 Nov '13, 23:05

question was seen: 16,921 times

last updated: 17 Jun '16, 21:53