Eratosthenes Sieve (Python)

Algorithm to find prime numbers that are less than or equal to a specified integer

procedure

  1. Get the top of the serial number list
  2. Store serial numbers in multiple list
  3. Remove multiples of serial numbers from the serial number list 4.3 Repeat 3 to the end of the serial number list
  4. Repeat 1-4 until the beginning of the sequence number list is greater than or equal to the square root of the input value.
  5. The numbers remaining in the serial number list and multiple list are prime numbers

Normal code

# coding: utf-8

import sys
import math


if __name__ == '__main__':
    #Standard input
    #Enter one number per line
    #Ctrl to finish input+Press Z and Enter(for Windows)
    input_list = sys.stdin.readlines()

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

        if 2 > num:
            continue

        # 1.Create a serial number list of input values
        # 2, 3,Remove multiples of 5 in advance
        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.The beginning of the serial number list ends with the square root of the input value or more
        while math.sqrt(num) >= serial_number_list[0]:

            # 2.Store serial numbers in multiple list
            multiple_list.append(serial_number_list[0])
                        
            # 4.Repeat until the end of the serial number list
            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.Remove multiples of serial numbers from serial number list
                    serial_number_list.remove(serial_number)

        # 6.The numbers remaining in the serial number list and multiple list are prime numbers
        print(multiple_list + serial_number_list)

Fast version

--Sequential numbers are managed by index --Manage whether it is a prime number or not with boolean

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

reference

[Wikipedia-Eratosthenes Sieve](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 --Eratosthenes Sieve Do your best to speed up the Eratosthenes sieve

Recommended Posts

Eratosthenes Sieve (Python)
Python
kafka python
Python Summary
Built-in python
Python comprehension
Python technique
Studying python
Python 2.7 Countdown
Python FlowFishMaster
Python service
python tips
python function ①
Python basics
Python memo
ufo-> python (3)
Python comprehension
install python
Python basics ④
Python Memorandum 2
python memo
Python Jinja2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Python memo
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
Python summary
[Python] Sort
Python basics ③
python log
[Scraping] Python scraping
Python update (2.6-> 2.7)
python memo
Python memorandum
Python # sort
ufo-> python
Python nslookup
python learning
Hannari Python 2020
[Rpmbuild] Python 3.7.3.
Solve AtCoder Beginner Contest 170 D --Not Divisible (ABC170D) with python (Eratosthenes sieve)
Prorate Python (1)
python memorandum
Download python
python memorandum
Python memo
started python
Python #JSON
python quiz
Python encoding