Майже прості числа#1302

Майже прості числа (Розбір)

Майже прості називаються такі натуральні числа, які мають вигляд $p^{k}$ p^k, де $p$ — просте число, а $k \geq 2$ k \ge 2. Наприклад, майже простими є числа: $4, 8, 16, 32, 9, 81, ...$ 4, 8, 16, 32, 9, 81, ... .

Оскільки $hi g h < 1 0^{12}$ high < 10^{12}, то, виходячи з визначення майже простого числа, можливі значення простого числа $p$ задовольняють нерівність $p < 1 0^{6}$ p < 10^6.

Згенеруємо масив $p r im es$ довжини $1 0^{6}$ 10^6, де $p r im es [i] = 1$ primes[i] = 1, якщо $i$ — просте число, і $p r im es [i] = 0$ primes[i] = 0 в іншому випадку.

Далі сформуємо масив $m$ , який містить усі майже прості числа, не перевищуючі $1 0^{12}$ 10^{12}. Кількість таких чисел складе $80070$ , і відсортуємо їх за зростанням.

Позначимо через $f (a, b)$ f(a, b) кількість майже простих чисел у відрізку $[a .. b]$ . Тоді

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)

Кількість майже простих чисел на відрізку $[1.. n]$ дорівнює індексу, в який можна вставити число $n$ в масив $m$ , щоб зберегти його впорядкованість.

Цей індекс можна знайти за допомогою бінарного пошуку — функцією upper_bound.

Приклад

Згенеруємо всі майже прості числа в проміжку від $1$ до $100$ .

Спочатку запишемо степені простого числа $2$ , не перевищуючі $100$ :

4, 8, 16, 32, 64

4, 8, 16, 32, 64

Потім запишемо степені $3$ :

9, 27, 81

9, 27, 81

Потім запишемо степені $5$ :

25

І нарешті, запишемо степені $7$ :

49

Квадрат числа $11$ дорівнює $121$ , що більше $100$ , тому степені $11$ і більше не потрапляють в заданий діапазон.

Після сортування отримаємо масив:

Розглянемо другий тест: $[1; 20]$ . У цьому діапазоні знаходяться наступні майже прості числа: $4, 8, 9, 16$ 4, 8, 9, 16. Їх кількість дорівнює $4$ .

Реалізація алгоритму

Оголосимо глобальні масиви. Майже прості числа, не перевищуючі $1 0^{12}$ 10^{12}, представляють собою степені простих чисел, не перевищуючих $M A X = 1 0^{6}$ MAX = 10^6.

Усі знайдені майже прості числа будемо зберігати в масив $m$ .

#define MAX 1000010
char primes[MAX];
long long m[MAX];

Для перевірки чисел на простоту заздалегідь згенеруємо масив $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++

Основна частина програми.

gen_primes();

Для кожного простого числа $i$ заносимо в масив $m$ його степені $i^{2}, i^{3}, i^{4}, ...$ i^2, i^3, i^4, ..., поки чергова ступінь не перевищить $1 0^{12}$ 10^{12}. Змінна $pt r$ містить кількість майже простих чисел, доданих у масив $m$ . Оскільки значення майже простих чисел не перевищують $1 0^{12}$ 10^{12}, для зберігання і обчислень необхідно використовувати $64$ -бітові цілі числа (тип long long).

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++

Сортуємо масив $m$ за допомогою стандартної бібліотеки STL.

sort(m,m+ptr);

Читаємо кількість вхідних тестів $t es t s$ і для кожного інтервалу $[l, h]$ обчислюємо і виводимо значення

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

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

Кожен такий запит обробляється за час $O (l o g_{2} pt r)$ O(log_2~ptr) з використанням бінарного пошуку.

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 реалізація

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