소수 - 에라토스테네스의 체

인프런 김태원 강사님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Uiep

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

https://inf.run/Uiep문제

내가 기존에 생각했던 소수 찾는 함수

#내 풀이
n = int(input())

def is_prime(x):
    if x < 2:
        return False
    for i in range(2, n+1):
        if x % i == 0:
            return False
    return True

cnt = 0
for i in range(1, n+1):
    if is_prime(i):
        cnt += 1

print(cnt)

위 방식은 입력값으로 받는 숫자 x에 대하여 2 ~ x-1번까지,

즉 x-2번의 연산이 필요하며 이는 시간복잡도 O(x)로 표현할 수 있겠다.

하지만 시간초과가 나서 x의 범위를 조금 더 줄였다.

 

#내 풀이
n = int(input())

def is_prime(x):
    if x < 2:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

cnt = 0
for i in range(1, n+1):
    if is_prime(i):
        cnt += 1

print(cnt)

 

기존 for문이 2에서 N-1까지 돌았던 것을 2에서 N의 제곱근까지만 돌도록 처리해주어

연산 횟수를 절반으로 줄일 수 있다.

이 방법으로는 시간제한안에 통과할 수 있었다.

---

강의에서는 에라토스테네스의 체 방법을 이용했다.

#강의 풀이
n = int(input())
ch = [0] * (n+1)
cnt = 0
for i in range(2, n+1):
    if ch[i] == 0:
        cnt += 1
        for j in range(i, n+1, i):
            ch[j] = 1

print(cnt)

이 방법은 n+1 칸의 배열을 0으로 생성하고,

index를 기준으로 2부터 진행하면서 0이라면 소수 count 변수에 1을 해준다.

그 후에 count +1을 해준 수의 배수들을 모두 배열 값을 1로 변경하면서

마지막까지 진행하는 방식이다.

 

이 방식의 알고리즘은 거의 상수시간과 가까울 정도로 빠른 시간 내에 연산을 가능하게 해줄수 있다고 한다.

 

참고 사이트 : https://seongonion.tistory.com/43