2023.04.21 풀이
import sys
input=sys.stdin.readline
import math
m,n=map(int, input().split())
arr=[True]*(n+1)
arr[1]=False
for i in range(2, int(math.sqrt(n))+1):
if arr[i]==True:
j=2
while i*j<=n:
arr[i*j]=False
j+=1
for j in range(m,n+1):
if arr[j]==True:
print(j)
다른 풀이
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
d = [False, False] + [True] * (m-1)
primes, res = [], []
for i in range(2, m+1):
if d[i]:
for j in range(i*i, m+1, i):
d[j] = False
for i in range(n, m+1):
if d[i]:
print(i)
check point
- arr[1] 주의
- 에라토스테네스의 체 : 여러 개의 수가 소수인지 아닌지 판별할때
a. 2~n 까지 모든 자연수 나열
b. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 찾기
c. 남은 수 중에서 i의 배수 모두 제거(i는 제거 x)
d. 더 반복할 수 없을 때까지 b,c 반복
-> 배수 지우기
import math
n=1000
arr=[True for i in range(n+1)]
for i in range(2, int(math.sqrt(n)+1):
if arr[i]==True:
j=2
while i*j<=n:
arr[i*j]=False
j+=1
for i in range(2, n+1):
if arr[i]==True:
print(i, end=" ")