Почему не генерирует простые числа в Python, использующие сеты таким образом?

У меня есть стандартный алгоритм, который я использую для генерации простых чисел (возможно, не самый эффективный, но он работает так же хорошо, как и он мне нужен), и я подумал, что немного оптимизирую его, используя таблицы вместо списков. Однако, когда я использую набор, я получаю числа, такие как 143 и 989, которые не являются первичными, и я не уверен, почему это так. Ниже мой стандартный код, который я использую для генерации простых чисел с меткой '' ', где я бы использовал набор вместо списка.

import math prime = [2, 3] # prime = set([1, 2]) def prime_checker(a): b = int(math.sqrt(a)) + 1 for j in prime: if a % j == 0: return False if j > b: break for i in range (5, 100000, 2): if prime_checker(i) != False: prime.append(i) # prime.add(i) 

По какой-то причине это всегда срабатывает, если я ищу только простые числа менее 100, но как только я продлю эту ссылку, я начинаю получать простые числа.

Когда вы используете set вы повторяете простые числа в случайном порядке. Это означает, что даже первый штрих, который вы выполняете, может быть больше b что приводит к завершению цикла и добавлению числа к результату.

Если вы удалите ранний перерыв, вы получите тот же результат:

 def prime_checker(a): #b = int(math.sqrt(a)) + 1 for j in prime: if a % j == 0: return False #if j > b: # break 

Наборы неупорядочены, но (из-за деталей реализации в стандартном интерпретаторе Python CPython) наборы, которые включают только последовательные (или почти последовательные) маленькие целые числа, будут иметь свои значения в порядке, особенно если это порядок, который они добавили в набор.

Однако, поскольку содержимое набора становится более разреженным (как набор простых чисел), вероятность больших значений, возникающих между меньшими элементами в порядке итерации, возрастает. Ваш алгоритм полагается на порядок простых чисел в вашей prime последовательности, так как вы прекратите цикл после того, как увидите первое значение, большее, чем sqrt(a) . Так как набор растет, все больше и больше вероятность того, что ваш первичный чек не будет работать правильно.

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

Чтобы быть простым, число должно быть только делящимся само по себе и одним – поэтому добавление проверки для этого решит. Вы получаете квадратный корень из 143 -> b = 12 + 1 = 13 , но он также делится на 11, и это не проверяется, вы завершаете его до его проверки.

Поскольку вы только добавляете в основной список после того, как 2,3 уже существуют и превышают 5-1000000, вам нужно

 def prime_checker(a): for j in range(a): if a % j == 0: return False #if j > b: #break # we've iterated and verified return True 

В противном случае вы никогда не проверяете числа, которые находятся в рассылке, так как они фактически не добавляются.

Как говорили другие, Python устанавливает, как правило, не поддерживает порядок добавления элементов, поэтому ваше условие цикла может попытаться проверить делимость на простое, которое слишком велико для текущего a . Вы можете использовать набор здесь, но вам нужно использовать диапазон (или какой-либо другой способ создания пробных факторов в порядке), а затем вы можете проверить, находятся ли эти пробные факторы в наборе простых чисел.

Вот модифицированная версия вашего кода, которая делает это. Он печатает содержимое набора primes чтобы вы могли видеть, что они не упорядочены.

Обратите внимание, что я использую a ** 0.5 для вычисления квадратного корня, вместо того, чтобы импортировать функцию sqrt из math библиотеки. Это не только позволяет сохранить import , но и операторы быстрее, чем вызовы функций.

 primes = {2, 3} def prime_checker(a): if a in primes: return True for j in range(2, int(a ** 0.5) + 1): if j in primes and a % j == 0: return False return True hi = 200 for i in range (5, hi, 2): if prime_checker(i): primes.add(i) print(len(primes)) print(primes) print(*sorted(primes)) 

вывод

 46 {2, 3, 131, 5, 7, 137, 11, 139, 13, 17, 19, 149, 23, 151, 29, 157, 31, 163, 37, 167, 41, 43, 173, 47, 179, 53, 181, 59, 61, 191, 193, 67, 197, 71, 199, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127} 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 

Короткое замыкание оператора and оператора, что означает, что в

 if j in primes and a % j == 0: 

если тест j in primes тестах терпит неудачу, то тест a % j == 0 не будет выполнен.


BTW, ваша функция prime_checker возвращает False если число не проходит тест primality, но возвращает значение по умолчанию None если тест завершается; это немного странно. 🙂 И False и None рассматриваются как false-ish, т. Е. Если v является False или None то if a: будет терпеть неудачу.

В руководстве по стилю Python PEP-0008 рекомендуется не проверять явно против True или False :

Не сравнивайте значения boolean с True или False с помощью == .

Да: if greeting:
Нет: if greeting == True:
Хуже: if greeting is True:

т.е. вместо

 if some_condition == False: 

ты должен сделать

 if not some_condition: 

Конечно, это не будет работать в вашем коде из-за проблемы False / None упомянутой выше.


FWIW, есть очень хороший код для быстрого поиска, чтобы указать все простые числа ниже N. Этот вопрос довольно старый, поэтому большинство ответов для Python 2, но их достаточно легко преобразовать в Python 3.

Другой способ проверить, является ли число простым или нет:

 import math def is_prime(n): if n % 2 == 0 and n > 2: return False return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))