⭐⭐⭐소수 구하기

자연수 N 이하의 소수 개수를 출력하는 프로그램을 작성하세요.

이때 소수란 양의 약수가 자기 자신과 1만 존재하는 수를 말합니다.

또한 어떤 정수 A가 어떤 정수 B의 약수라는 것은 B를 A로 나누었을 때 나누어떨어짐을 의미합니다.

 

[입력값 설명]

『첫 번째 줄에 1 이상 1000 이하의 자연수 N이 주어집니다.』

[출력값 설명]

『1 이상 N 이하의 자연수 중에서의 소수의 개수를 출력합니다.』

------------------------------------------------------------------------

예제 입력1

978

예제 출력1

165

예제 입력2

99

예제 출력2

25

 

---

import sys
input = sys.stdin.readline

N = int(input())

ans = 0
for n in range(2, N+1):		# 2부터 N까지 
    ans += 1				# 일단 n 자기 자신 
    for s in range(2, n):	# 2부터 n까지 
        if (n%s == 0):		# n이 s에 나눠 떨어지면 그건 소수가 아님 
            ans -= 1		
            break
print(ans)

 

 

에라토스테네의 체 1 

import sys
input = sys.stdin.readline

N = int(input())

primes = [True] * (N + 1)
primes[0] = primes[1] = False  # 0과 1은 소수가 아님

for i in range(2, int(N**0.5) + 1):		# 효율성을 위해 절반만 탐색함 
    if primes[i]:						
        for j in range(i*i, N + 1, i):
            primes[j] = False
print(sum(primes))

 

에스토스테네의 체 2 

import sys
input = sys.stdin.readline

N = int(input())
lst = list(range(2, N+1))

i = 0
l = len(lst)
while i < l:
    for j in range(lst[i]+1, N+1):
        if j % lst[i] == 0:
            while j in lst:
                lst.remove(j)
    l = len(lst)
    i += 1
print(len(lst))