STUDY_SEONMIN

1929. 소수 구하기 본문

STUDY/Baekjoon Algorithm

1929. 소수 구하기

Kululu_ 2021. 7. 14. 16:30

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.(1MN1,000,000)

- 에라토스테네스의 체를 이용하세요.

 

n = 1000000
sieve = [True] * (n+1)
m = int(n**0.5)

for i in range(2, m+1):
    if sieve[i] == True:
        for j in range(i+i, n+1, i):
            sieve[j] = False
sieve[0], sieve[1] = False, False

M, N = map(int, input().split())

for i in range(M, N+1):
    if sieve[i] == True:
        print(i)

 

 

  • 먼저 구하고자하는 범위에 대해 에라토스테네스의 체를 만들어줍니다.
    - sieve[i]가 곧 숫자 i가 소수인지 아닌지를 의미하게끔 만들었습니다.

  • M이상 N이하의 숫자 중에서 소수인 숫자들만 출력하는 것은 M부터 N까지의 for문을 돌리는 것으로 구현했습니다.

'STUDY > Baekjoon Algorithm' 카테고리의 다른 글

9020. 골드바흐의 추측  (0) 2021.07.15
4948. 베르트랑 공준  (0) 2021.07.14
11653. 소인수분해  (0) 2021.07.12
2581. 소수  (0) 2021.07.12
1978. 소수 찾기  (0) 2021.07.12
Comments