[GO] Tamis Eratostenes (édition Python)

Algorithme pour trouver les nombres premiers qui existent sous l'entier spécifié

procédure

1. Obtenez le haut de la liste des numéros de série
2. Stockez les numéros de série dans plusieurs listes
3. Supprimez les multiples de numéros de série de la liste des numéros de série 4.3 Répéter 3 jusqu'à la fin de la liste des numéros de série
4. Répétez 1-4 jusqu'à ce que le début de la liste des numéros de série soit supérieur ou égal à la racine carrée de la valeur d'entrée.
5. Les numéros restants dans la liste des numéros de série et la liste multiple sont des nombres premiers

Code normal

# coding: utf-8

import sys
import math


if __name__ == '__main__':
    #Entrée standard
    #Entrez un numéro par ligne
    #L'entrée de fin est Ctrl+Appuyez sur Z et Entrée(for Windows)
    input_list = sys.stdin.readlines()

    for num in input_list:
        num = int(num.replace('\n', ''))

        if 2 > num:
            continue

        # 1.Créer une liste de numéros de série de valeurs d'entrée
        # 2, 3,Multiples de 5 pré-supprimés
        multiple_list = [2, 3, 5]
        serial_number_list = [r for r in range(2, num + 1) if r % 2 != 0 and r % 3 != 0 and r % 5]
                
        # 5.Le début de la liste des numéros de série se termine par la racine carrée de la valeur d'entrée ou plus
        while math.sqrt(num) >= serial_number_list[0]:

            # 2.Stocker les numéros de série dans plusieurs listes
            multiple_list.append(serial_number_list[0])
                        
            # 4.Répétez jusqu'à la fin de la liste des numéros de série
            for serial_number in range(serial_number_list[0], serial_number_list[- 1] + 1,  serial_number_list[0]):
        
                if serial_number in serial_number_list:
                    
                    # 3.Suppression des multiples de numéros de série de la liste des numéros de série
                    serial_number_list.remove(serial_number)

        # 6.Les numéros restants dans la liste des numéros de série et la liste multiple sont des nombres premiers
        print(multiple_list + serial_number_list)

Version rapide

• Les nombres séquentiels sont gérés par index --Boolean gère s'il s'agit d'un nombre premier

import math


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        
        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False


if __name__ == '__main__':
    while True:
        try:
            n = int(input())
        except:
            break
        
        input_list = sieve_of_erastosthenes(n)
        prime_list = [i for i, b in enumerate(input_list) if b == True]
        print(prime_list)
        print(sum(prime_list))

référence

[Wikipedia-Eratostenes Sift](http://en.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86 % E3% 83% 8D% E3% 82% B9% E3% 81% AE% E7% AF% A9) peria.jp --Eratostenes tamis Faites de votre mieux pour accélérer le tamis Eratostenes