Быстро определить, является ли число простым в Python для чисел <1 млрд.

Question

Мой текущий алгоритм проверки простоты чисел в python - это способ замедления для чисел от 10 миллионов до 1 миллиарда. Я хочу, чтобы это улучшилось, зная, что я никогда не получу числа, превышающие 1 миллиард.

Ситуация в том, что я не могу получить реализацию, которая достаточно быстра для решения проблемы 60 проекта Эйлера: я получаю ответ на проблему за 75 секунд, где она мне нужна за 60 секунд. http://projecteuler.net/index.php?section=problems&id=60

У меня очень мало памяти, поэтому я не могу хранить все простые числа ниже 1 млрд.

В настоящее время я использую стандартное пробное деление, настроенное на 6k ± 1. Есть ли что-нибудь лучше, чем это? Нужно ли уже получать метод Рабина-Миллера для таких больших чисел?

primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def isprime(n):
    if n <= 100:
        return n in primes_under_100
    if n % 2 == 0 or n % 3 == 0:
        return False

    for f in range(5, int(n ** .5), 6):
        if n % f == 0 or n % (f + 2) == 0:
            return False
    return True

Как я могу улучшить этот алгоритм?

Точность: я новичок в python и хотел бы работать только с python 3+.

---

Окончательный код

Для тех, кому интересно, используя идеи MAK, я сгенерировал следующий код, который примерно на 1/3 быстрее, что позволяет мне получить результат проблемы Эйлера менее чем за 60 секунд!

from bisect import bisect_left
# sqrt(1000000000) = 31622
__primes = sieve(31622)
def is_prime(n):
    # if prime is already in the list, just pick it
    if n <= 31622:
        i = bisect_left(__primes, n)
        return i != len(__primes) and __primes[i] == n
    # Divide by each known prime
    limit = int(n ** .5)
    for p in __primes:
        if p > limit: return True
        if n % p == 0: return False
    # fall back on trial division if n > 1 billion
    for f in range(31627, limit, 6): # 31627 is the next prime
        if n % f == 0 or n % (f + 4) == 0:
            return False
    return True

Answer 1

Для чисел до 10 ^ 9 одним из подходов может быть генерация всех простых чисел до sqrt (10 ^ 9), а затем просто проверка делимости входного числа на числа в этом списке.Если число не делится на любое другое простое число, меньшее или равное его квадратному корню, оно само должно быть простым (у него должен быть хотя бы один фактор <= sqrt и другой> = sqrt, чтобы не быть простым).Обратите внимание, что вам не нужно проверять делимость для всех чисел, вплоть до квадратного корня (а это около 32 000 - мне кажется, вполне управляемым).Вы можете сгенерировать список простых чисел, используя sieve .

. Вы также можете пройти вероятностный простой тест .Но их может быть сложнее понять, и для этой проблемы достаточно просто использовать сгенерированный список простых чисел.

Answer 2

Для решения задач Project Euler я сделал то, что вы предлагаете в своем вопросе: внедрил тест Miller Rabin (в C #, но я подозреваю, что он будет быстр и в Python).Алгоритм не так сложен.Для чисел ниже 4 759 123 231 достаточно проверить, что число является сильным псевдопростым числом для оснований 2, 7, 61. Объединить это с пробным делением на маленькие простые числа.Вы уже решили, но наличие быстрого теста на первичность в вашем распоряжении будет иметь большое значение для многих проблем.

Answer 3

Ну, у меня есть продолжение моего комментария под (очень хорошим) ответом Питера Ван Дер Хейдена о том, что в «популярных» библиотеках Python нет ничего хорошего для действительно больших простых чисел (чисел в целом). Оказывается, я был не прав - в sympy есть одна (отличная библиотека символической алгебры, среди прочих):

https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.primetest.isprime

Конечно, это может дать ложные срабатывания выше 10**16, но это уже намного лучше, чем все остальное, что я мог бы сделать, ничего не делая (кроме, может быть, pip install sympy;))

Answer 4

Вы можете сначала разделить ваш n только на primes_under_100.

Кроме того, предварительно вычислите больше простых чисел.

Кроме того, вы фактически сохраняете свой результат range() в памяти - используйте irange() вместо этого и используйте эту память для запуска Алгоритм сита Эратосфена .

Answer 5

def isprime(num):
if (num==3)or(num==2):
    return(True)
elif (num%2 == 0)or(num%5 == 0):
    return (False)
elif ((((num+1)%6 ==0) or ((num-1)%6 ==0)) and (num>1)):
    return (True)
else:
    return (False)

Я думаю, что этот код самый быстрый ..