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

×

CDFI4 - Editorial

PROBLEM LINK

Contest

DIFFICULTY

MEDIUM

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.

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

asked 13 Oct '16, 21:54

intayush's gravatar image

3★intayush
41
accept rate: 0%

edited 07 Jun '17, 17:16

admin's gravatar image

0★admin ♦♦
19.7k350498541

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:

×2,556
×300
×9
×1

question asked: 13 Oct '16, 21:54

question was seen: 356 times

last updated: 07 Jun '17, 17:16