[알고리즘] 소수

📌

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

✔️ 내가 짠 코드

 

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

n=int(input())
count=0

for i in range(2, n+1):
    output=[]
    for j in range(1, i+1):
        if i % j == 0:
            output.append(j)
    if len(output) == 2:
        count += 1

print(count)

 

>>>

 

2의 배수와 제곱근을 제외시켜야하나 라고 고민할 것이 아니었다.

실행시켜보니 15, 49 ... 조건문만 복잡해졌다.

1 ~ i+1 까지 돌면서 약수를 리스트에 집어넣고,

리스트의 길이가 2면 1과 자기 자신만을 약수로 가진 수이기 때문에 약수이다. 따라서 len() 메소드로 답을 구했다.

 

그런데 실제 코드는 에라토스테네스 체를 이용해 훨씬 효율적으로 답을 구했다.

망할.

 

 

 

에라토스테네스 체

 

ex ) 1 ~ 20 까지 수가 있다고 했을 때, 배수들을 걸러내는 작업이다.

 

< 초기 설정 >

ch = [0] * (n+1)

index  1 2 3 4 … 20

                                                                value  0 0 0 0 … 0

 

i = 2 ~n 까지 for 문으로 돌면서 if ch[index] 값이 0 이면 소수이므로 count += 1 해주는 형식이다.

 

 

 

✔️ 실제 코드 

 

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)