[백준 1929] 소수구하기

1. 문제

 

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

2. 접근방법

 

예전에 모르고리즘 문제 중 소수 판별하기 문제가 있었는데 그 문제 풀면서 사용했던 "에라토스테네스의 체"가 생각나서 이걸로 풀었습니다.

 

사실 그거 이름만 기억나고 구현 방법은 기억이 안나서 ^-^

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

서치 했구요 ..

 

A형 시험 D-3인데 .. 잘 할 수 있겠쬬 ..?

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

흠 ~!

 

에라토스테네스의 체

출처 : wikidocs.net/21638

위키독스

 

3. 파이썬 코드

 

M, N = map(int, input().split())
a = [False, False] + [True]*(N-1)
primes = []

for i in range(2, N+1):
    if a[i]:
        if M <= i <= N:
            primes.append(i)
        for j in range(2*i, N+1, i):
            a[j] = False

print(*primes, sep="\n")

 

4. 마치며

온겸쓰가 풀어보라고 해서 푼 문제인데

에라토스테네스의 체를 기억할 겸 .. 첫 포스팅도 해볼겸 .. 적은 글이구요

알고리즘 풀이 포스팅 스켈레톤은 알고리즘 신 갓승환님의 포스팅을 참고했습니다

 

그럼 이만 ~!