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