Простые числа меньше или равно п

Question

В заявлении говорится:

Написать функцию era1() которая запрашивает у пользователя число n, а затем использовать этот алгоритм, чтобы напечатать все простые числа меньше или равно n.

Алгоритм:

• Написать список с номерами от 2 до наибольшего целого числа N вы хотите вычислить.
• Первое число в списке - простое число. Напишите это число в списке простых чисел, B.
• Удалить из списка A, первый элемент и его кратность.
• Если первое число в списке A меньше квадратного корня N, вернитесь ко второй точке.
• Номера в списке B и те, что остались в списке A, являются обычными.

Теперь я ставлю этот код:

import math 

def primo(num): 
    if num < 2: 
     return False 

    i = 2 
    for i in range(2, int(math.sqrt(num) + 1)): 
     if (num % i == 0): 
      return False 

    return True 

def main(): 
    n = input("Introdueix un nombre: ") 
    B = range(2, n) 
    for i in B: 
     if primo(i): 
      print i   

main() 

def era1(): 
    n = input("Introdueix un nombre: ") 
    A = range(2, n + 1) 
    B = [A[0]] 

    for i in A: 
     if i % 2 == 0: 
      A.remove(i) 

    if A[0] < math.sqrt(n): 
     print B + A 

era1() 

Результат неверен, потому что если я удалить один из входных данных, появляется ошибка, и я должен поставить только один раз вход. Также результат неверен, потому что A + B, список B не является списком функций main, а конечным результатом являются только числа, не кратные 2 и 2. Как я могу поместить только один вход, а затем окончательный результат будет правильным?

Answer 1

Извлечение элементов из списка при выполнении итераций по нему будет иметь неожиданные результаты, это мешает индексированию.

a = [1,2,3,4,5,6,7,8,9] 
for thing in a: 
    a.remove(thing) 


>>> a 
[2, 4, 6, 8] 
>>> 

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

Answer 2

Этот алгоритм называется Sieve of Eratosthenes.

Это простой алгоритм для нахождения всех простых чисел до заданного целого числа . Он был создан в 3 веке до н.э. Эратосфен, древнегреческий математик.

Для разработки этого алгоритма мы рассмотрим различные вышеупомянутые этапы.

• Сначала мы сгенерируем список с числами от 2 до наибольшего целого числа N, которое вы хотите вычислить.

A = range(2, n + 1) 

• Мы используем другой список C, как мы могли бы использовать позже, чтобы напечатать первоначальный список.

• Мы проходим через C, обрабатывая все числа меньше, чем квадратный корень N.

• инициализируем пустой список B, и добавить каждый раз, когда простое число (который является первым элементом списка).
• Мы используем понимание списка для умножения фильтров с использованием: (x%firstElement!=0).

С = [х при х в С, если х% firstElement! = 0]

• Б является объединением остальных чисел (простые числа, которые больше, чем площади корень N) и простые числа, которые мы уже обнаружили.

Ваш код должен выглядеть следующим образом:

def era1(): 
    n = input("Introduce a nombre: ") 
    #n=120 #To test the 
    A = range(2, n + 1) 
    B, C= [],A 
    while C[0]< math.sqrt(n): #Condition 
     firstElement= C[0] 
     B+= [firstElement] #The first number in the list is a prime number. Write this number a list of primes, B. 
     C= [x for x in C if x%firstElement!=0] #We use comprehension List to filter multiplies using 
    return B+C#The numbers in the B list and those left in List A are all primes searched. 

print era1() 

выход в случае п = 120: [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]

Эта картина Visualize Алгоритм, Source of picture.