[Python/알고리즘] 인프런 소수의 개수 구하기

문제출처

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

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

---

풀이코드

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

n = int(input())
cnt = 0

for x in range(2, n+1):
    if prime(x):
        cnt += 1
print(cnt)

---

코드설명

1. 소수는 1과 자기 자신 이외의 어떤 양의 정수로도 나누어 떨어지지 않는 자연수

2. 1은 소수가 아니기 때문에 2부터 시작

3. 어떤 숫자로도 나누어 떨어진다면 False를 반환하여 소수가 아님을 나타내는 것을 함수화

4. 개수를 구하기 위해 prime(x)를 입력하여 소수 인것들만 반환하여 cnt에 대입

5. 최종 소수 갯수 출력

---

기타사항

#에라토스테네스의 체 구현
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)

 

1. ch에 0이 들어있는 리스트를 배열함

2. 배열에 0이 들어가있다면 cnt에 카운트 대입

3. 2의 배수, 즉 n의 배수들은 나누어 떨어지기 때문에 소수가 아니므로 ch[j]에 1을 대입해서 소거

4. 최종 소수 갯수 출력