### 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 ≤ 10 ^{9}**.

### EXPLANATION:

### APPROACH 1:

First of all let’s try to see how number of factors is derived from prime factorisation:

If a number **N = p _{1}^{a1} * p_{2}^{a2} * … p_{N}^{aN}**, where

**p**are prime numbers, then number of factors of

_{i}**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** = **P _{k}**, 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**P**where_{k}**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(10**in this set.^{9})

### 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[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);
}
}
```