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

소수를 구하는 법

1. n까지 범위에서 약수를 찾기

n = int(input())
cnt = 0

for x in range(2, n+1):
    for i in range(2, x):  # range(2, 2)일때는 빈 범위 생성 -> for문 안이 실행되지x
        if x % i == 0:
            break
    else:
        cnt += 1


print(cnt)

다음과 같이 n까지의 범위를 두고 찾아도 되지만 비효율적이다.

2. n**0.5까지 범위에서 약수를 찾기

n = p * q

n = 루트n * 루트n

그러므로 무조건 한쪽은 n의 0.5승 이하.

따라서 n**0.5까지의 범위를 두고 나눠지는지 확인하면 더 효율적이다.

for x in range(2, n+1):
    for i in range(2, int(x**0.5)+1):  # range(2, 2)일때는 빈 범위 생성 -> for문 안이 실행되지x
        if x % i == 0:
            break
    else:
        cnt += 1


print(cnt)

💡 에라토스테네스 체

하지만 위와 같은 방법은 n이 소수인지 확인할 때 적합하고
n 이하의 소수를 구하려면 오래걸림

에라토스테네스 체 : n 이하의 소수를 구할 때 가장 빠르게 구할 수 있는 방법

• 배수를 다 지워버림으로서 체를 치듯이 숫자를 거름

구하는 법

1. n+1길이의 배열을 만듦 (인덱스 번호가 해당하는 숫자)
2. 배열을 0으로 초기화함
3. che[i]가 0이면 소수라고 판단
4. i의 배수를 다 1로 바꿔버림 (che[j] = 1)

n 이하의 소수의 숫자를 세시오

n = int(input())
cnt = 0
che = [0] * (n+1)   // 1. 배열 만들고 초기화

for i in range(2, n+1):
    if che[i] == 0:  // 2. 값이 0이면 소수
        cnt += 1
        for j in range(i, n+1, i):   // 3. i의 배수는 값을 1로 바꿔주기(쳐내기)
            che[j] = 1
    else:
        continue

print(cnt)