백준-1929

소수 구하기 문제로서 내가 알고있는 소수를 구하는 방법은 두가지 있다.
1. 무식하게 숫자하나를 2부터 해당 숫자-1까지 다 나눠보고 소수를 판단한다.
2. 에라토스테네스의 체를 사용한다.

• 1의 방법에서는 해당숫자-1 까지가 아닌 int(숫자^0.5)+1 까지만 해도 된다.
• 에라토스테네스의 체 알고리즘은 다음과 같다.
  • 1) 기준 숫자만큼 공간을 만든다
  • ex) ans = [0, 0] + [1]*(n-1) --> 0과1은 제외한다.
  • 2) 위 공간에서 1인 숫자는 primes이라는 소수 공간에 저장한다.
  • 3) 그리고 저장한 숫자에 대한 모든 배수는 0으로 처리하여 소수로 저장할 수 없게 한다.
  • 4) 위의 과정을 반복한다.

m, n=map(int, input().split())

ans=[0, 0] + [1]*(n-1)
primes=[]

for i in range(2, n+1):
    if ans[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            ans[j]=0

for i in primes:
    if m<=i<=n:
        print(i)