Мое основное сито с использованием Python

print("Welcome to the Sieve of Eratosthenes, where you can generate prime numbers from 1 to n  : ")
n = int(input("Enter your n :   "))
y = [y for y in range(1,n) if y*y < n]
primes = [p for p in range(2,n+1)]
length = len(primes)

print(primes)

for p in range(2,len(y)+2):
    
    for i in range(2,length+1):
        if(i%p == 0 and i != p ):
            if(i in primes):
                primes.remove(i)
        
                
print(primes)
            


"""
1.)A range  //0 to 100  .x
2.)Multiples can be found using 1 to sqrt(n) .x
3.)Now eliminate all multiples. x
"""

ВЫХОД

Введите ваш номер : 20
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 2, 3, 5, 7, 11, 13, 17, 19]

Итак, я сделал это самостоятельно, а также мне нужны некоторые предложения о том, что я могу сделать, чтобы улучшить код, и можете ли вы сказать мне, насколько он хорош?

print("Welcome to the Sieve of Eratosthenes, where you can generate prime numbers from 1 to n  : ")

Это не Сито Эратосфена. Это простое решето в том смысле, что оно берет список чисел и удаляет (или отсеивает) те, которые не являются простыми. Но это не следует алгоритму Решета Эратосфена.

Вот как выглядит Решето Эратосфена:

primes = [p for p in range(2, n + 1)]

for p in primes:
    if p > n / p:
        break

    for i in range(p * p, n + 1, p):
        if i in primes:
            primes.remove(i)

Это не обязательно оптимальная версия (например, может быть лучше сравнить p к квадратному корню из n а не делать n / p каждый раз; или может быть лучше использовать набор, а не список). И вряд ли он будет самым питоническим. Я не занимаюсь разработкой на Python, поэтому вам не следует воспринимать все, что я предлагаю, как Pythonic.

Некоторые вещи, которые это делает, чего нет в вашей версии:

1. Он работает только с простыми числами. Начальный цикл может выглядеть так, как будто он повторяется по всему диапазону. Но на самом деле он перебирает только простые числа, потому что не простые числа удаляются до того, как они достигаются (я тестировал и, в отличие от PHP, Python перебирает текущую версию массива, а не копию оригинала). Он начинается с 2 и исключает все четные числа.
2. Это не пробное деление. Вместо этого он использует метод Эратосфена, кратный текущему простому числу.

Эта часть об умножении, а не делении — это то, что я бы назвал центральным принципом алгоритма решета Эратосфена. Поэтому, когда я говорю, что ваша версия не является Решетом Эратосфена, я имею в виду, что она этого не делает.

Примечание: нет ничего плохого в реализации другого сита. Можно написать лучше (хотя я не уверен, что это лучше). Решето Эратосфена примечательно тем, что оно относительно хорошее, а также понятное при умеренных усилиях. Это не самое эффективное сито. Я просто говорю, что не стоит называть вашу версию Решетом Эратосфена, так как она им не является.

Стилистические улучшения

• Вы создаете список yи используйте его только для верхней границы первого цикла. Граница должна быть квадратным корнем из n, вы можете вычислить это напрямую. Так for p in range(2, math.ceil(n**0.5) + 1) вместо for p in range(2, len(y)+2).
• В Python вам не нужны (и не должны использоваться) круглые скобки для if заявления. if i in prime это то же самое, что if (i in prime).
• Если вы внимательно посмотрите, то заметите, что length точно так же, как n-1. Это на самом деле ошибка, так как вы включаете номер n в список primes потенциальных простых чисел. Например, если n = 99это не устранит 99 из-за этого. В любом случае, вы можете просто использовать n вместо length.

После этих предложений и исправлений ошибок вы получите следующий код:

import math
n = int(input())

primes = [p for p in range(2, n + 1)]
for p in range(2, math.ceil(n**0.5) + 1):
    for i in range(2, n + 1):
        if i % p == 0 and i != p:
            if i in primes:
                primes.remove(i)

print(primes)

Алгоритмические улучшения

Давайте сначала запустим программу для n = 100 000. На моем ноутбуке запуск кода занимает около 2,5 минут.

Одна большая ошибка заключается в том, что вы используете список для хранения потенциальных простых чисел. Если вы сохраняете потенциальные числа на бумаге, на самом деле довольно быстро найти, есть ли число в списке, потому что числа упорядочены по нарастающей. Также легко удалить номер. Например, если вы хотите удалить число 4 из списка, вы знаете, что оно находится в самом начале, и вы можете просто вычеркнуть его ручкой. Однако Python не знает, что этот список монотонно увеличивается. Если вы хотите удалить номер 4 из списка 100 000 номеров, то он должен проверить все 100 000 номеров, так как любой из них может быть номером 4. Таким образом, вы тратите много времени. С точки зрения сложности оба поиска чисел (if i in primes) и удаление числа primes.remove(i) равно O(n)).

Существуют и другие структуры данных, которые могут выполнять обе операции намного быстрее. Самый простой — просто использовать Python set. А set это просто структура данных, которая может содержать кучу разных чисел. Его не волнует порядок или частота ввода числа ({1, 2} == {2, 1, 1} является True в Python), однако вы можете выполнять поиск очень быстро, а также очень быстро удалять значения. Оба в O (1) в Python.

И в качестве примечания. if i in primes: primes.remove(i) такой же как primes.discard(i). discard удаляет элемент из набора, если он есть, и ничего не делает, если его там нет.

import math
n = int(input())

primes = set(range(2, n + 1))
for p in range(2, math.ceil(n**0.5) + 1):
    for i in range(2, n + 1):
        if i % p == 0 and i != p:
            primes.discard(i)

print(sorted(primes))

Обратите внимание, что мы сортируем оставшиеся числа в конце, поскольку набор в Python не сохраняет данные в отсортированном порядке (по крайней мере, это не гарантируется).

Для того же входа (n = 100 000), теперь код выполняется примерно за 2,7 секунды. Почти ускорение 60x.

Если вы немного изучите решето Эратосфена, то поймете, что вам нужно всего лишь вычеркнуть кратные простые числа. например мы i == 6 не нужно вычеркивать кратные числа 6 больше, потому что мы вычеркнули их уже тогда, когда мы вычеркнули кратные 2 (и фактически второй раз, когда мы зачеркнули кратные 3).

Это означает, что мы можем сделать следующую оптимизацию:

import math
n = int(input())

primes = set(range(2, n + 1))
for p in range(2, math.ceil(n**0.5) + 1):
    if p in primes:
        for i in range(2, n + 1):
            if i % p == 0 and i != p:
                primes.discard(i)

print(sorted(primes))

Для ввода n = 100 000 теперь это выполняется всего за 0,7 секунды.

Еще одна оптимизация может заключаться в следующем. В настоящее время вы работаете i по всем числам и проверьте, кратны ли они p. Но вы также можете просто перебрать все кратные p напрямую. Поскольку мы знаем, что все кратные p находятся 2*p, 3*p, 4*p, 5*p, ...вы можете просто запустить следующее:

import math
n = int(input())

primes = set(range(2, n + 1))
for p in range(2, math.ceil(n**0.5) + 1):
    if p in primes:
        for k in range(2, n // p + 1):
            primes.discard(k * p)

print(sorted(primes))

Теперь это выполняется всего за 0,12 секунды для ввода n = 100 000. Общее ускорение более чем в 1000 раз, начиная с исходного кода.