Тема: Генерирование простых чисел
Может кто-то сможет подсказать метод генерирования простых числе от 1 до 10^9 в количестве до 100,000 (т.е., на вход подается массив номеров простых чисел, на выход возвращаются сами простые числа) ?
Re: Генерирование простых чисел
Вы имеете в виду "дано k, найти k-е простое число, и так 10^5 раз"?
Одно k-е (1 <= k <= N) простое число я умею искать в лучшем случае за O(N^{2/3})
Все простые от 1 до N за O(N).
Re: Генерирование простых чисел
Да, подразумевается массив k = {k1, k2, ..., km}, m <= 10^5. Требуется вывести p(ki) -- ki-ое простое число (первое простое число -- 2, второе 3 и т.д.)
Re: Генерирование простых чисел
Burunduk1 пишет:
Вы имеете в виду "дано k, найти k-е простое число, и так 10^5 раз"?
Одно k-е (1 <= k <= N) простое число я умею искать в лучшем случае за O(N^{2/3})
Все простые от 1 до N за O(N).
O(N^{2/3}) с массивом констант или без?
Re: Генерирование простых чисел
Ссылка на задачу https://www.spoj.pl/problems/KPRIMES2/