1302. Почти простые числа

Натуральное число называется почти простым, если оно не является простым, но при этом имеет ровно один простой делитель.

Найдите количество почти простых чисел в заданном интервале натуральных чисел.

Вход. Первая строка содержит количество тестов n (n £ 600).

Каждая из последующих n строк представляет отдельный тест и содержит два числа low и high (0 < low £ high < 10¹²).

Выход. Для каждого теста выведите в отдельной строке количество почти простых чисел в промежутке [low.. high] включительно.

Пример входа	Пример выхода
3 1 10 1 20 1 5	3 4 1

РЕШЕНИЕ

решето Эратосфена - бинарный поиск

Анализ алгоритма

Почти простыми называются такие натуральные числа, которые имеют вид p^k, где p – простое число, а k ³ 2. Например, почти простыми являются числа: 4, 8, 16, 32, 9, 81, … .

Поскольку high < 10¹², то исходя из определения почти простого числа, возможные значения простого числа p удовлетворяют неравенству p < 10⁶.

Сгенерируем массив primes длины 10⁶, где primes[i] = 1, если i – простое число, и primes[i] = 0 в противном случае.

Далее сформируем массив m, содержащий все почти простые числа, не превышающие 10¹². Количество таких чисел составит 80070, и отсортируем их по возрастанию.

Обозначим через f(a, b) количество почти простых чисел в отрезке [a..b]. Тогда

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

Затем запишем степени 3:

9, 27, 81

Затем запишем степени 5:

25

И наконец, запишем степени 7:

49

Квадрат числа 11 равен 121, что больше 100, поэтому степени 11 и выше не попадают в заданный диапазон.

После сортировки получим массив:

Рассмотрим второй тест: [1; 20]. В этом диапазоне находятся следующие почти простые числа: 4, 8, 9, 16. Их количество равно 4.

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

Объявим глобальные массивы. Почти простые числа, не превышающие 10¹², представляют собой степени простых чисел, не превышающих MAX = 10⁶.

Все найденные почти простые числа будем сохранять в массив m.

#define MAX 1000010

char primes[MAX];

long long m[MAX];

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

}

Основная часть программы.

gen_primes();

Для каждого простого числа i заносим в массив m его степени i², i³, i⁴, …, пока очередная степень не превысит 10¹². Переменная ptr содержит количество почти простых чисел, добавленных в массив m. Поскольку значения почти простых чисел не превышают 10¹², для хранения и вычислений необходимо использовать 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;

}

}

Сортируем массив m с помощью стандартной библиотеки STL.

sort(m,m+ptr);

Читаем количество входных тестов tests и для каждого интервала [l, h] вычисляем и выводим значение

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

Каждый такой запрос обрабатывается за время O(log₂ 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);

}

}

}