# AMR14E - Editorial

Editorialist: Lalit Kundu

EASY-MEDIUM

### PRE-REQUISITES:

Prime Numbers, Number Theory, Segmented Seive

### PROBLEM:

Given A, B (B - A ≤ 200000), find the count of integers in range A to B which have prime number of distinct factors.
A, B ≤ 109.

### APPROACH 1:

First of all let’s try to see how number of factors is derived from prime factorisation:
If a number N = p1a1 * p2a2 * … pNaN, where pi are prime numbers, then number of factors of N is

So, for number of factors to be prime, there should only be a single prime factor of N otherwise number of factors will not be prime(a prime only has single factor).

So, let’s say N = Pk, where P is a prime. So, number of factors of N now will be k+1, so k+1 should also be prime. So, if we are checking if a number N has prime number of factors, there are two cases:

1. If N is prime, then it’s valid. For checking such large primes we’ll need segmented seive. We can use the same concept used in this problem.
2. Else, N should be a perfect square(otherwise k+1 will be even). Also, sqrt(N) should be present in a set S which stores all numbers of form Pk where P is a prime and 2k + 1 is prime. We can manually build this set in very less complexity because we don’t need numbers larger than sqrt(109) in this set.

### APPROACH 2:

We use segmented seive. We find all prime numbers till sqrt(R) and then build a seive, where seive[i] stores number of factors of L+i. The following pseudo code will make it clear.

``````bool isPrime;
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;
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);
}
}
``````

### SOLUTIONS:

Setter’s solution

Can you point out the error in the following code…

I have used the same approach as in the editorial…

http://www.codechef.com/viewsolution/5900846

Can anyone point out the case at which i am getting WA …

We can do this problem by actually finding the number of factor of each number from A-B using segmented sieve. And see for each whether its a prime number. The code would be more neat and shorter and there won’t be any need to handle cases separately.

@karanaggarwal - I used segmented sieve to find number of factors for each number in L-R and then checked if it was prime or not but that timed out as it was O ((no of primes till sqrt®)*(l-r)*log®) for each test case in my implementation. Could you highlight optimizations/tricks that I have missed ?

I found out primes till sqrt 10^9 using sieve.
Then I used these primes to find the number of factors for each no in L-R.

We have to modify the segmented sieve concept slightly to find out the number of factors, instead of using a sqrt(N) approach to find the number of factors of N.
Overall Complexity of the solution would be O(N*logN)

@karanaggarwal can u please expand on “we have to modify the segmented sieve concept slightly” ?
Thanks.