Тест первичности в python

Я пытаюсь сделать простой тест прочности в Python.

Согласование с Википедией, тест на первичность заключается в следующем:

Учитывая входное число n, проверьте, не делит ли любое целое число m от 2 до n – 1. Если n делится на любое m, то n является составным, в противном случае оно является простым.

Я начал с исключения четных чисел – за исключением 2 – в качестве кандидатов на премьер

def prime_candidates(x): odd = range(1, x, 2) odd.insert(0, 2) odd.remove(1) return odd 

Затем записывая функцию для проверки простых чисел, в соответствии с приведенными выше правилами.

 def isprime(x): for i in range(2, x-1): if x % i == 0: return False else: return True 

И это основная функция, которая перебирает список из 8000 основных кандидатов и проверяет их простоту

 def main(): end = 8000 candidates = prime_candidates(end) for i in candidates: if isprime(i) and i < end: print 'prime found ' + str(i) 

Проблема в том, что функция isprime возвращает True для чисел, которые не являются простыми.

isprime(x) говоря, ваш isprime(x) проверяет, является ли число нечетным, выходящим сразу после if x % 2 == 0 .

Попробуйте небольшое изменение, чтобы вы действительно перебирали:

 def isprime(x): for i in range(2, x-1): if x % i == 0: return False else: return True 

Обратите внимание, что else: теперь является частью цикла for а не оператора if .

Посмотрите на тест примитивности Миллера-Рабина, если будет достаточно вероятностного алгоритма. Вы также можете доказать, что число должно быть простым, например, с помощью проверки эллиптической кривизны (ECPP) , но для этого требуется больше усилий.

Простым алгоритмом пробного деления является следующее

 def prime(a): return not (a < 2 or any(a % x == 0 for x in range(2, int(a ** 0.5) + 1))) 

Изменить: вот более образовательная версия, потому что первое решение очень сжато и, возможно, труднее читать:

 from math import sqrt def prime(a): if a < 2: return False for x in range(2, int(sqrt(a)) + 1): if a % x == 0: return False return True 

Я заменил в sqrt(a) вместо a ** 0.5 чтобы сделать вещи более ясными. Квадратный корень используется, чтобы не смотреть на большее количество факторов, чем нам нужно.

Ваша функция действительно возвращает ли ваш номер нечетным.

Действительно, что вы делаете, вы проверяете, 2 ли делит ваш номер и немедленно возвращается. Вы никогда не проверяете другие цифры.

То, что вам нужно сделать, это вернуть это значение true из предложения if else и цикла for в тело основной функции.

Если вы ищете простые числа ниже заданного числа, вы можете сохранить простые числа, найденные вами в памяти, а затем попробуйте делить ваш новый номер на эти простые числа! (так как если d является составной и делит q, то p существует такое, что p является простым и p делит q).

Проблема в том, что вы положили return False в предложение else , а не в конце функции. Таким образом, ваша функция вернется сразу после проверки первого делителя, а не для проверки других делителей.

Вот простой пример прочности, аналогичный вашему:

 def is_prime(n): d = 2 while d * d <= n: if n % d == 0: return False d += 1 return n > 1