구현 문제 #7. 소수 (에라토스테네스 체)

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

내 풀이 (제한시간 초과)

 

1. for문을 이용해 각 숫자의 약수가 총 몇개인지 알아본다.

2. 소수는 약수가 1과 자기자신이므로 2개만 존재한다. 따라서 약수가 2개인 숫자라면 소수이기때문에 결과 값 res를 1증가시킨다.

 

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

n = int(input())

res=0

for i in range(2,n+1):
    cnt=0
    for j in range(1,i+1):
        if i%j==0:
            cnt+=1
    if cnt==2:
        res +=1
print(res)

 

 

 

강사님 풀이

 

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

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): #i씩 증가
            ch[j]=1

print(cnt)

 

 

 

배운 점

 

1. 주어진 문제가 순차적으로 알아봐야 하는 문제라면, 배열의 인덱스를 의미있는 값으로 정하고 배열을 사용한다.

2. for문은 최대한 필요한 때에만 사용해서 소요시간을 절약한다.