STUDY_SEONMIN
1929. 소수 구하기 본문
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.(1≤M≤N≤1,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