[알고리즘] 에라토스테네스의 체

Hyo Kyun Lee·2022년 1월 14일
0

알고리즘

목록 보기
15/45

15. 에라토스테네스의 체

Sieve of Eratosthenes, 대량의 소수를 한꺼번에 판별 및 출력하는 알고리즘이다.

소수(prime number)는 자기자신과 1을 약수를 가지는 수이며, 에라토스테네스의 체는 특정 범위까지 소수를 출력한다.

15-1. 소수판단

1개의 수에 대한 소수여부를 파악하고자 하면, 수의 범위가 대칭을 이룬다는 점을 이용하여(한 수의 제곱근으로 범위를 줄여 판단 후 소수여부 확인) 해당 수의 제곱근까지만 소수인지 판단하면 된다.

#소수찾기

import math

def isPrimeNumber(n):
    end = int(math.sqrt(n))
    for i in range(2, end):
        if n % i == 0:
            return False
    return True

print(isPrimeNumber(97))

number = 1000
numberArray = [0] * (number + 1)

15-2. 에라토스테네스의 체

에라토스테네스의 체는 특정 수까지 모든 소수를 출력하는 알고리즘이다.
하나의 배열에 모든 수를 넣고, 2부터(2는 제외) 2의 배수를 차례로 제거한 후 최종적으로 남은 수(소수)를 출력한다.

number = 1000
numberArray = [0] * (number + 1)

def primeNumberSieve(number):
    for i in range(2, number):
        numberArray[i] = i
    for i in range(2, number):
        if numberArray[i] == 0:
            pass
        else:
            for j in range (i+i, i, number):
                numberArray[j] = 0
    for i in range(2, number):
        if numberArray[i] != 0:
            print(numberArray[i])

primeNumberSieve(number)

0개의 댓글