PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
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.
EXPLANATION:
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:
- 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.
- 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® 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[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);
}
}