소수(에라토스테네스 체)

문제

• N을 입력한 다음 1부터 N까지의 소수 개수를 출력하는 프로그램을 작성하라
• 만약 20이 입력된다면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개이다.
• 제한시간은 1초이다.

문제 풀이

import sys
sys.stdin = open("input.txt", "r")

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)

• ch라는 0으로 초기화한 리스트를 만들어 2의 배수 3의 배수 ... 해당 소수의 배수는 해당 소수가 약수이기 때문에 소수의 조건을 만족하지 않는다. 이런 규칙을 사용해 2중 for문을 돌며 해당 수의 배수들은 전부 1로 만들어 처리해준다.

내 오답

import sys
#sys.stdin = open("input.txt", "r")

def isPrime(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

n = int(input())
cnt=0

for i in range(2, n+1):
    if isPrime(i) == True:
        cnt += 1
print(cnt)

• 제한 시간이 있어서 문제가 RuntimeError가 발생했다.
• 기존에 풀었던 것처럼 isPrime이라는 소수 판별 함수를 만들어 n까지 돌면서 소수인지 확인하고 소수가 맞다면 cnt를 1씩 증가하는 방식으로 풀었지만 시간 제한에 걸렸다.