1302. Almost Prime Numbers

A positive integer is called almost prime if it is not a prime number but has exactly one prime divisor.

Determine the number of almost prime numbers within a given interval of positive integers.

Input. The first line contains the number of test cases n (n ≤ 600).

Each of the following n lines represents a separate test case and contains two numbers low and high (0 < low £ high < 10¹²).

Output. For each test case, print the number of almost prime numbers in the interval [low…high], inclusive.

Sample input	Sample output
3 1 10 1 20 1 5	3 4 1

SOLUTION

sieve of Eratosthenes – binary search

Algorithm analysis

Almost prime numbers are positive integers of the form p^k, where p is a prime number and k ³ 2. For example, the numbers 4, 8, 16, 32, 9, 81, … are all almost prime numbers.

Since high < 10¹², based on the definition of an almost prime number, the possible values of the prime number ppp must satisfy the inequality p < 10⁶.

We’ll generate an array primes of length 10⁶, where primes[i] = 1 if i is a prime number, and primes[i] = 0 otherwise.

Next, we construct an array m containing all almost prime numbers not exceeding 10¹². The number of such values is 80070, and we sort them in ascending order.

Let f(a, b) represent the number of almost prime numbers in the range [a..b]. Then:

f(low, high) = f(1, high) – f(1, low – 1)

The number of almost prime numbers in the range [1 .. n] is equal to the index at which number n can be inserted into array m to maintain its sorted order.

This index can be found using binary search – via the upper_bound function.

Example

Let’s generate all almost prime numbers in the range from 1 to 100.

First, write down the powers of the prime number 2 that do not exceed 100:

4, 8, 16, 32, 64

Then, write down the powers of 3:

9, 27, 81

Then, the powers of 5:

25

And finally, the powers of 7:

49

The square of 11 is 121, which is greater than 100, so the powers of 11 and higher primes do not fall within the given range.

After sorting, we get the array:

Let’s now consider the second test case: [1; 20]. In this range, the following almost prime numbers are found: 4, 8, 9, 16. Their total count is 4.

Algorithm implementation

Let’s declare global arrays. Almost prime numbers that do not exceed 10¹² are powers of prime numbers that do not exceed MAX = 10⁶.

All the found almost prime numbers will be stored in the array m.

#define MAX 1000010

char primes[MAX];

long long m[MAX];

To check whether numbers are prime, we’ll generate the array primes.

void gen_primes(void)

{

for (int i = 0; i < MAX; i++) primes[i] = 1;

for (int i = 2; i < sqrt(MAX); i++)

if (primes[i])

for (int j = i * i; j < MAX; j += i) primes[j] = 0;

}

The main part of the program.

gen_primes();

For each prime number i, add its powers i², i³, i⁴, … to the array m, until the current power exceeds 10¹². The variable ptr holds the number of almost prime numbers added to the array m. Since the values of almost prime numbers do not exceed 10¹², we need to use 64-bit integers (type long long) for storage and calculations.

for(i = 2; i < MAX; i++)

if (primes[i])

{

long long temp = 1LL*i*i;

while(temp < 1LL*MAX*MAX)

{

m[ptr++] = temp;

temp *= i;

}

}

Sort the array m using the STL standard library.

sort(m,m+ptr);

Read the number of input test cases tests, and for each interval [l, h], compute and print the value

f(l, h) = f(1, h) – f(1, l – 1)

Each such query is processed in O(log₂ ptr) time using binary search.

scanf("%d", &tests);

while(tests--)

{

scanf("%lld %lld", &l, &h);

printf("%d\n", upper_bound(m,m+ptr,h) - upper_bound(m,m+ptr,l-1));

}

Java implementation

import java.util.*;

public class ex

{

public static ArrayList<Long> primes = new ArrayList<Long>();

public static void GenPrimes()

{

final int MAX_SIZE = 1000001;

BitSet bits = new BitSet(MAX_SIZE);

bits.set(2, MAX_SIZE, true);

for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)

{

if (bits.get(i))

for (int j = i * i; j < MAX_SIZE; j += i)

bits.set(j, false);

}

for (int i = 2; i < MAX_SIZE; i++)

if (bits.get(i))

{

long temp = i;

while ((temp *= i) < 1000000000000L)

primes.add(temp);

}

primes.add(1000000000001L);

Collections.sort(primes);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

GenPrimes();

for(int i = 0; i < tests; i++)

{

Long low = con.nextLong();

Long high = con.nextLong();

int lIndex = Collections.binarySearch(primes, low);

if (lIndex < 0) lIndex = -(lIndex + 1);

int hIndex = Collections.binarySearch(primes, high);

if (hIndex < 0) hIndex = -(hIndex + 1); else hIndex++;

System.out.println(hIndex - lIndex);

}

}

}