Almost Prime Numbers#1302

Almost Prime Numbers (Editorial)

Almost prime numbers are positive integers of the form $p^{k}$ p^k, where $p$ is a prime number and $k \geq 2$ k \ge 2. For example, the numbers $4, 8, 16, 32, 9, 81, ...$ 4, 8, 16, 32, 9, 81, ... are all almost prime numbers.

Since $hi g h < 1 0^{12}$ high < 10^{12}, based on the definition of an almost prime number, the possible values of the prime number $p$ must satisfy the inequality $p < 1 0^{6}$ p < 10^6.

We'll generate an array $p r im es$ of length $1 0^{6}$ 10^6, where $p r im es [i] = 1$ primes[i] = 1 if $i$ is a prime number, and $p r im es [i] = 0$ primes[i] = 0 otherwise.

Next, we construct an array $m$ containing all almost prime numbers not exceeding $1 0^{12}$ 10^{12}. The number of such values is $80070$ , and we sort them in ascending order.

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

f (l o w, hi g h) = f (1, hi g h) - f (1, l o w - 1)

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

4, 8, 16, 32, 64

Then, write down the powers of $3$ :

9, 27, 81

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$ 4, 8, 9, 16. Their total count is $4$ .

Algorithm implementation

Let's declare global arrays. Almost prime numbers that do not exceed $1 0^{12}$ 10^{12} are powers of prime numbers that do not exceed $M A X = 1 0^{6}$ MAX = 10^6.

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 $p r im es$ .

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

C++

The main part of the program.

gen_primes();

For each prime number $i$ , add its powers $i^{2}, i^{3}, i^{4}, ...$ i^2, i^3, i^4, ... to the array $m$ , until the current power exceeds $1 0^{12}$ 10^{12}. The variable $pt r$ holds the number of almost prime numbers added to the array $m$ . Since the values of almost prime numbers do not exceed $1 0^{12}$ 10^{12}, 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;
    }
  }

C++

Sort the array $m$ using the STL standard library.

sort(m,m+ptr);

Read the number of input test cases $t es t s$ , and for each interval $[l, h]$ , compute and print the value

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

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

Each such query is processed in $O (l o g_{2} pt r)$ O(log_2~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 Main
{
  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);
    }
  }
}

Java