CODECHEF NOV13 PRETNUM

Problem Statement

Given a range a to b, we have to all numbers which have prime number of divisors.

Eg: In the range 1 to 10 , the numbers are 2, 3, 4, 5, 7, 9

For a brief problem statement visit this link.

Solution

what is a divisor ? If ‘x’ divides ‘y’, then ‘x’ is a divisor of ‘y’. Eg: ‘2’ is a divisor of ‘4’.

PROBLEM ANALYSIS :

• We need to count numbers having prime number of divisors. Except 2, all primes are odd numbers. This shows that we need to look for only numbers having odd number of divisors. Only Square Numbers  have odd number of divisors.
• Only prime numbers have 2 divisors

Thus, the problem is reduced to finding ” PRIME NUMBERS ” and “SQUARE NUMBERS“(which are prime) within the given range.

Pre-requisites

Sieve of Eratosthenes:

Let  us  say that u need to find primes upto ‘n’.

First make a list of numbers from 2 to n

Then, take the number ‘2’ and remove all multiples from the list. Then take the next number ( 3 ), then remove its multiples. Then, the take the next number ‘5’ and remove its multiples. Continue this process until the end of list.

Note: 4 is not taken as it is removed from the list by 2.

---

EFFICIENT WAY TO FIND NUMBER OF DIVISORS OF A NUMBER:

Let us consider a number ‘x’

The number x can be expressed in terms of prime numbers

x = ( p₁ )^e₁ * (p₂) ^e₂ * (p₃) ^e₃ * . . . . . . . . . . . . * (p_k) ^e_k

Eg: 36  = 2² * 3²

Number of divisors of number = ( 1 + e₁ ) * (1 + e₂) * ……… * (1 + e_k)

Eg: For 36, it is ( 1 + 2 ) * ( 1 + 2 ) = 9

EFFICIENT WAY TO FIND NUMBER OF PRIME NUMBERS IN A RANGE( a, b ):

In the Problem Statement , it is specified that a and b  can take values from 1 to 10 ^ 12.

Range ( b – a ) is <= 10 ^ 6

We can use Sieve of Eratosthenes, to compute prime numbers in a range quickly. I used the idea from this popular blog.

Example:

Say we need to find prime numbers from ‘10′ to  ’30’.

First, create a list called primes which contain prime numbers upto SQRT(30).  The primes list will contain numbers 2, 3, 5.

Then, make a list called result of size of 21 ( 30 – 10 + 1 ). The index ‘0’ in this list correspond to ’10’ and index ’20’ correspond to ’30’.

Take the first prime ‘2’ from primes list .Find multiple of 2 which is nearest to 10.

It is ’10’. Its index is ‘0’. Set the flag for that index false and remove all the multiples of ‘2’ from the result list.

Now, take all primes from the list and continue the same process.

CODE:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
#define LL long long
vector<int> primes;
vector<bool> isPrime(1000001,false);

void precompute()
{
	vector<bool> flag(1000001,true);
	int i,j,k;
	primes.push_back(2);
	isPrime[2] = true;

	for(i=3;i<=1000001;i+=2)
		if( flag[i] )
		{
			primes.push_back(i);
			isPrime[i] = true;
			for( j = i,k = i*2; j <= 1000001; j+=k )
				flag[j] = false;
		}
}

int divisors(int num)
{
	int cnt = 0,finalCount = 1,i = 0;
	bool is = false;

	while( i < primes.size() && num > 1 )
	{
		cnt = 0;
		while( num > 1 && num % primes[i] == 0 )
		{
			num /= primes[i];
			cnt++;
		}

		if( cnt )
			is = true;

		finalCount *= (cnt*2 + 1);
		i++;
	}
	if( num > 1 )
		finalCount *= 3;

	if( is )
		return finalCount;

	return 0;
}

int countPrimes(long long int l,long long int r)
{
	if( l == 1LL )
		l++;
	vector<bool> fc(1000002,true);
	int i = 0,cnt,low,high = r - l,k;

	while( i < primes.size() )
	{
		long long int first = l + ( primes[i] - (l % primes[i]) ) % primes[i];

		if( first == primes[i] )
			first += primes[i];

		low = first - l;

		while( low <= high )
		{
			fc[low] = false;
			low += primes[i];
		}

		i++;
	}
	cnt = 0;
	i = 0;
	while( i <= high )
	{
		if( fc[i] )
			cnt++;
		i++;
	}

	return cnt;
}

int findCount(long long int l,long long int r)
{
	int low = sqrt(l);
	int d,count = 0;

	if( ((LL)low * (LL)low) < l )
		low++;

	while( ( (LL)low * (LL)low )  <= r )
	{
		d = divisors(low);
		if( isPrime[d] )
			count++;
		low ++;
	}

	return count;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	precompute();
	int t;
	cin>>t;
	while(t--)
	{
		long long int l,r;
		cin>>l>>r;
		cout<<findCount(l,r) + countPrimes(l,r)<<"\n";
	}
}