m,n=map(int,input().split())
for i in range(m,n+1):
if i==1:#1은 소수가 아니므로 제외
continue
for j in range(2,int(i**0.5)+1):
if i%j==0: #약수가 존재하므로 소수가 아님
break #더이상 검사할 필요가 없으므로 멈춤
else:
print(i)
에라토스테네스의 체(소수 구하기) 문제이다.
int(i**0.5)+1
까지이다. 특정 수의 제곱근을 구해, 그 제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다(소수가 아니기에). 이렇기 때문에 범위를 위와같이 설정해주었다.1부터 12 사이의 소수를 판별해본다.
1은 소수가 아니므로 2부터 시작한다.
12<4^2이므로(int(sqrt(12))=3) 4보다 작은 수의 배수만 제거하면 된다.(즉, 3까지만 계산)
자기자신을 제외한 2의 배수를 다 제거한다.
남아있는 숫자 중(기존에 제거한 숫자는 또 제거할 필요가 없다.) 자기자신을 제외한 3의 배수를 다 제거한다.
남은 수 중에서 1을 제외하고 [2, 3, 5, 7, 11]이 1부터 12사이의 소수가 된다.
에라토스테네스의 체를 사용하면 모든 숫자를 검사할 필요가 없으므로(검사해야하는 범위가 클수록 효과적) 시간 복잡도도 감소한다.
O(N) -> O(N^(1/2))
답안으로 구하신건 체로 구하신게 아닌디요..?