[GO] Eratostenes Sieb (Python Edition)

Algorithmus zum Finden von Primzahlen, die unterhalb der angegebenen Ganzzahl existieren

Verfahren

1. Holen Sie sich den Anfang der Seriennummernliste
2. Speichern Sie Seriennummern in mehreren Listen
3. Entfernen Sie mehrere Seriennummern aus der Seriennummernliste 4.3 Wiederholen Sie 3 bis zum Ende der Seriennummernliste
4. Wiederholen Sie 1-4, bis der Anfang der Seriennummernliste größer oder gleich der Quadratwurzel des Eingabewerts ist.
5. Die in der Seriennummernliste und der Mehrfachliste verbleibenden Nummern sind Primzahlen

Normaler Code

# coding: utf-8

import sys
import math


if __name__ == '__main__':
    #Standardeingabe
    #Geben Sie eine Nummer pro Zeile ein
    #Endeingabe ist Strg+Drücken Sie Z und die Eingabetaste(for Windows)
    input_list = sys.stdin.readlines()

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

        if 2 > num:
            continue

        # 1.Erstellen Sie eine Seriennummernliste mit Eingabewerten
        # 2, 3,Vorab entfernte Vielfache von 5
        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.Der Anfang der Seriennummernliste endet mit der Quadratwurzel des Eingabewerts oder mehr
        while math.sqrt(num) >= serial_number_list[0]:

            # 2.Speichern Sie Seriennummern in mehreren Listen
            multiple_list.append(serial_number_list[0])
                        
            # 4.Wiederholen Sie diesen Vorgang bis zum Ende der Seriennummernliste
            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.Vielfache von Seriennummern aus der Seriennummernliste entfernt
                    serial_number_list.remove(serial_number)

        # 6.Die in der Seriennummernliste und der Mehrfachliste verbleibenden Nummern sind Primzahlen
        print(multiple_list + serial_number_list)

Schnelle Version

--Sequenznummern werden nach Index verwaltet --Boolean verwaltet, ob es sich um eine Primzahl handelt

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))

Referenz

[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-Sieb Geben Sie Ihr Bestes, um das Eratostenes-Sieb zu beschleunigen