Dev 달팽이 @_''

[파이썬] 백준 1929 번 : 소수 구하기 본문

PS/Python

[파이썬] 백준 1929 번 : 소수 구하기

다본죽 2021. 2. 17. 01:51

출처 : www.acmicpc.net/problem/1929

 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

소수를 N^2 보다 작은 시간복잡도로 푸는 대표적인 방법인 에라토스테네스의 체를 이용하여 구하였다.

에라토스테네스의 체에 대해서 아래 링크에 매우 잘 설명되어있다.

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
MAX = 1000000
 
prime = [0]*(MAX+1)
prime[0] = prime[1] = True
 
for i in range(2,MAX+1):
    if not prime[i]:
        j = i+i
        while j<= MAX:
            prime[j] = True
            j += i
 
n,m = map(int,input().split())
 
for i in range(n,m+1):
    if prime[i] == False:
        print(i)
 
 cs
저작자표시 (새창열림)

'PS > Python' 카테고리의 다른 글

[파이썬] 백준 17425 번 : 약수의 합  (0) 2021.02.17
[파이썬] 백준 6588 번 : 골드바흐의 추측  (0) 2021.02.17
[파이썬] 백준 2609 번 : 최대공약수와 최소공배수  (0) 2021.02.17
[파이썬] 백준 17427 번 : 약수의 합2  (0) 2021.02.17
[파이썬] 백준 1037 번 : 약수  (0) 2021.02.17
'PS/Python' Related Articles more