PRETNUM - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY

PREREQUISITES:

Prime factorization, Sieve

PROBLEM:

Find the number of integers in the given range which have prime number of divisors.

QUICK EXPLANATION:

Although L and R can be as high as 10^12 but R-L is <= 10^6, this allows us to iterate through the complete range and count the number of divisors of each number in the range.

EXPLANATION:

Approach 1:
If a number N is divisible by D then either it has 2 factors(D and N/D) or it is square of D. Another thing to note is that if a number has 2 divisors x and y such that x < y, then x < sqrt(N) and y > sqrt(N). Using these 2 facts we can iterate through all the numbers in range [1, sqrt®] and count the number of factors for each of the number.

Working commented solution follows:

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);
	}
}

Approach 2:
This approach is taken by more coders including tester.
This is based on prime factorization of a number and then counting the total number of divisors.

Lets take an example:
Consider prime factors breakdown of 18 (2^1 * 3^2) so total number of factors are (1+1) * (2 + 1) = 6 [Factors: 1, 2, 3, 6, 9, 18]. Similarly if a number is p1^x1 * p2^x2 * p3^x3 * … then total number of factors is (x1+1) * (x2+1) * (x3+1) * …

Now if we generate all primes <= 10^6 using sieve and later use them to find out how many times it goes into each number in the given range, we know the number of divisors composed of primes <= 10^6. We may have missed 1 prime number > 10^6 which might have fallen in the range as range goes as high as 10^12. But we are sure that there is only 1 such prime! So if we detect this case we can simply multiply our number of factors calculated so far by (1+1). See tester’s solution for working code.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be uploaded soon
Tester’s solution can be found here and here

4 Likes

We don’t need to count factors of each numbers, only for perfect squares in the range, am i right?

Because apart from primes (2 factors), only perfect squares can have prime number of factors since only perfect squares have odd number of factors, other numbers have even number of factors(except 2 no of factors)

So we can calculate number of factors of only perfect squares and look that up to be prime between [1,200]

9 Likes

All we need to do is to count the no of numbers that are powers of prime such that power+1 is also prime!! :wink:

6 Likes

the numbers follow a pattern… p^(q-1) where both p and q are prime …
i used sieve to figure out all the prime numbers… and simple math to figure out how many numbers are powers of (prime-1) that comes within the given range of ‘l’ to ‘r’ … worked out well n good !!
http://www.codechef.com/viewsolution/2976601

3 Likes

CAN ANYONE TELL WHATS WRONG WITH MY CODE
http://www.codechef.com/viewsolution/2975377

Run time error for large inputs
http://ideone.com/qkLWfU

Declaring array every time: primes= new (nothrow) uint64[r];

Declare it global…

1 Like

Hi Admin,

Could you please tell me ans for 1000000 1000100
I have checked with some solutions those are giving answer as 6
but here is one accepted solution that is giving ans 5
http://www.codechef.com/viewplaintext/2977722

as we can see ans should be 6 [1000003,1000033,1000037,1000039,1000081,1000099]

Thanks,

2 Likes

Is this what you did?
2,3,5,7,11,…,999999999989
squares of 2,3,5,7,…,999983
power 4 of 2,3,5,7,…,997
power 6 of 2,3,5,7,…,97
power 10 of 2,3,5,7,11,13
power 12 of 2,3,5,7
power 16 of 2,3,5
power 18 of 2,3
power 22 of 2,3
power 28 of 2
power 30 of 2
and power 36 of 2
This is the pattern i could guess when i was working on this question. But then i got stuck because of the space constraint in C++. It can count the rest. The problem is only with the prime numbers after 10^6.
Can you help me with this?

@whizcode, sorry i couldn’t get to you soon … was occupied with december challenge.!
And no that wasn’t what i did, i just calculated all the prime numbers in that interval using seive and then used dp to calculate powers of (prime-1) in that interval, thats all the problem requires :slight_smile:

@shaleen

I didn’t get the part where you say "We may have missed 1 prime number > 10^6 which might have fallen in the range as range goes as high as 10^12. But we are sure that there is only 1 such prime! So if we detect this case we can simply multiply our number of factors calculated so far by (1+1) .

Also I think it should be the ((prime > 10^6) + 1) in the end,right ?

Find all perfect squares and prime numbers in the range [l,r].

Check if square root of a perfect square has exactly one prime divisor( is of the form prime^(k) ), because product of two numbers can never be prime.

Then original number is prime^(2k)
Number of divisors of prime^(2k) = 2k+1.

Then using sieve check if 2k+1 is prime.
If prime add 1 to answer.

Also add number of prime numbers between [l,r] to the answer.
my solution

1 Like

Any number from the range [1,10^12].
Will have following properties:

  1. Can either be a prime number
  2. Or will have atleast one prime number from range [1,10^6] in its prime factorisation.
  3. And it can not be product of two primes both >10^6.

It helped me in finding all primes in the range [l,r]

The no. in the range[l,r] let us say x should be a power of a single prime no. i.e its prime factorization should be of the form x = p^q where q + 1 is a prime.

The reason is that total no. of divisors of a no. with prime factorization (p1)^q1 * (p2)^q2… (pn)^qn will have total divisors = (q1 + 1)*(q2 + 1)…(qn + 1).

For total divisors of the form stated above to be prime. n should be 1. Since if its greater than 1 then no. of divisors will be composite.

Now n being 1, q1 + 1 should be prime!

runtime error(other) why the hell i am getting this