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

자연수 N이 입력되면 1부터 N까지의 숫자들 중 소수의 개수를 출력하는 프로그램을 작성!

ex) 20입력 시 1부터 20까지의 숫자들 중 소수는 2,3,5,7,11,13,17,19로 총 8개.

 

입력예시)

20

 

출력예시)

8

---

내가 처음 쓴 코드

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):
        cnt += 1

print(cnt)

---

모범답안

n = int(input())
checkLst = [0]*(n+1)
cnt = 0

for i in range(2,n+1):
    if checkLst[i] == 0:
        cnt += 1
        for j in range(i, n+1, i):
            checkLst[j] = 1

print(cnt)

---

모범답안 보고 느낀점!

• 나는 소수인가 아닌가를 판별하는 isPrime 함수를 정의해서 
  2부터 N까지 돌면서 하나하나 함수를 적용하고 True값이 나오면 cnt 변수를 하나씩
  증가하는 형태로 풀었는데, 모범답안은 접근방식이 아예 달랐다!
  내가 훨씬 단순하고 직관적인데 딱봐도 내가 훨씬 오래걸릴거같다.
  
  모범답안은 인덱스를 N까지 가지는 1차원 배열을 만들어 0으로 초기화하고,
  인덱스 2부터 돌면서 그 값이 0이면 (소수) cnt값을 하나씩 증가하고, 
  그 인덱스의 배수 인덱스들의 값을 1로 셋팅 (소수가 아니라는 뜻)하면서 진행하는 방식을 취했다.
  어쩌면 에라토스테네스 의 "체", 즉 걸러낸다는 의미를 조금 더 살린 방식이 아닐까.. 멋있다!
  
  인덱스 자체를 이용하는 방법을 주체적으로 생각하는 연습을 좀 해야겠당.
  아자아자~

 

---

모범답안 아이디어로 다시 작성해보기

n = int(input())
lst = [0]*(n+1)
cnt = 0

for i in range(2, n+1):
    if lst[i] == 0:
        cnt += 1
        for j in range(i, n+1, i):
            lst[j] = 1

print(cnt)