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

소수 판별하는 함수

하나하나 다 검사하기에는 비효율적이고 대칭을 이루기 때문에 특정한 숫자의 제곱근까지만 검사하면 된다.
ex)
소수면 True, 소수가 아니면 False를 출력

def isPrimeNumber(x):
    end=int(x**.5)
    for i in range(2,end):
        if x%i==0:
            return False
    return True

print(isPrimeNumber(97))

True

1. 이차원 배열 생성 후 초기화하기

자기자신은 지우지 않는다.

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 지운다.

먼저 2의 배수부터 지운다.

자기자신은 지우지 않는다.

3의 배수를 지운다.

이러한 과정들을 반복한다음 2부터 출력한다.

2,3,5,7,11,13,17,19,23가 25까지의 소수

number=100
a=[0]*101

def isPrimeNumber():
    for i in range(2,number+1): #그냥 배열에 숫자 채워넣기
        a[i]=i
    for i in range(2,number+1): #0이면 넘기기
        if a[i]==0:
            continue
        for j in range(i+i,number+1,i): #자기 자신이 아닌 배수는 0으로 바꾸기
            a[j]=0
    for i in range(2,number+1): #0이 아닌 수를 출력
        if a[i]!=0:
            print(a[i])
isPrimeNumber()

>>> 2
3
5
7
.
.
.
79
83
89
97