AMR14E - Editorial



Editorialist: Lalit Kundu




Prime Numbers, Number Theory, Segmented Seive


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.



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.


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) {
	    if (j * j > i) isPrime[i] = true;
	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++;


Setter’s solution

Can you point out the error in the following code…

I have used the same approach as in the editorial…

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” ?