Эффективно генерировать простые числа в Python и вычислять сложность

Question

Генерация простых чисел от 1 до n Python 3. Как повысить эффективность и в чем сложность?

Ввод: число, максимум (большое число) Выход: все простые числа от 1 до макс. Вывод в виде списка и будет [2,3,5,7,11,13, .......] Код пытается выполнить эту задачу эффективным способом (с наименьшей сложностью).

from math import sqrt    
max = (10**6)*3
print("\nThis code prints all primes till: " , max , "\n")
list_primes=[2]

def am_i_prime(num):
    """
    Input/Parameter the function takes: An integer number
    Output: returns True, if the number is prime and False if not
    """ 
    decision=True
    i=0
    while(list_primes[i] <= sqrt(num)): #Till sqrt(n) to save comparisons
        if(num%list_primes[i]==0):
            decision=False
            break
                    #break is inserted so that we get out of comparisons faster
                    #Eg. for 1568, we should break from the loop as soon as we know that 1568%2==0
        i+=1
    return decision


for i in range(3,max,2):  #starts from 3 as our list contains 2 from the beginning
    if am_i_prime(i)==True:
    list_primes.append(i)  #if a number is found to be prime, we append it to our list of primes

print(list_primes)

Как я могу сделать это быстрее? Где я могу улучшить? Какова временная сложность этого кода? Какие шаги неэффективны? Чем Сито Эратосфена более эффективно, чем это?

Работа для первых нескольких итераций: -

1. У нас есть list_primes, который содержит простые числа. Изначально он содержит только 2.
2. Переходим к следующему числу, 3. Делится ли 3 на любое из чисел в list_primes? Нет! Мы добавляем 3 к list_primes. Прямо сейчас, list_primes=[2,3]
3. Переходим к следующему номеру 4. Делится ли 4 на любое из чисел в list_primes? Да (4 делится на 2). Итак, мы ничего не делаем. Прямо сейчас list_primes=[2,3]
4. Переходим к следующему числу, 5. Делится ли 5 ​​на любое из чисел в list_primes? Нет! Мы добавляем 5 к list_primes. Прямо сейчас, list_primes=[2,3,5]
5. Мы переходим к следующему числу, 6. Делится ли 6 на любое из чисел в list_primes? Да (6 делится на 2, а также делится на 3). Итак, мы ничего не делаем. Прямо сейчас list_primes=[2,3,5]
6. И так далее ...

Answer 1

Интересно, что для доказательства правильности вашего алгоритма требуется довольно глубокая математическая теорема. Теорема такова: «Для каждого n ≥ 2 существует простое число между n и n ^ 2». Я знаю, что это было доказано, и гораздо более строгие границы доказаны, но я должен признать, что я не знаю, как доказать это сам. И если эта теорема не верна, то цикл в am_i_prime может выйти за границы массива.

Число простых чисел ≤ k равно O (k / log k) - это опять-таки очень глубокая математическая теорема. Опять за меня доказать.

Но в любом случае, существует около n / log n простых чисел до n, и для этих простых чисел цикл будет перебирать все простые числа до n ^ (1/2), и есть O (n ^ (1/2) ) / журнал п) из них.

Таким образом, для одних простых чисел время выполнения, следовательно, равно O (n ^ 1,5 / log ^ 2 n), так что это нижняя граница. Приложив некоторые усилия, можно доказать, что для всех чисел время выполнения асимптотически одинаково.

O (n ^ 1,5 / log n), очевидно, является верхней границей, но экспериментально число делений для нахождения всех простых чисел ≤ n представляется равным ≤ 2 n ^ 1,5 / log ^ 2 n, где log - натуральный логарифм .

Answer 2

Следующая перестановка и оптимизация вашего кода достигнут вашего максимума почти в 1/2 от времени вашего исходного кода. Он объединяет ваш цикл верхнего уровня и функцию предиката в единую функцию для устранения накладных расходов и более эффективно управляет квадратами (квадратными корнями):

def get_primes(maximum):
    primes = []

    if maximum > 1:
        primes.append(2)
        squares = [4]

        for number in range(3, maximum, 2):
            i = 0

            while squares[i] <= number:
                if number % primes[i] == 0:
                    break

                i += 1
            else:  # no break
                primes.append(number)
                squares.append(number * number)

    return primes

maximum = 10 ** 6 * 3
print(get_primes(maximum))

Тем не менее, алгоритм на основе сита легко справится с этим (поскольку он избегает деления и / или умножения). В вашем коде есть ошибка: установка max = 1 создаст список [2] вместо правильного ответа пустого списка. Всегда проверяйте оба конца своих пределов.

Answer 3

O (N ** 2)

Приблизительно говоря, первый вызов am_I_prime выполняет 1 сравнение, второй - 2, ..., поэтому общее количество равно 1 + 2 + ... + N, что составляет (N * (N-1 )) / 2, который имеет порядок N-квадрат.