백준 알고리즘 | 1929 : 소수 구하기 (Python / 파이썬)

---

소수 구하기 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	76024	21286	15073	27.483%

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

문제

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

​

입력

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

​

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

​

알고리즘 분류

수학

정수론

소수 판정

에라토스테네스의 체

---

백준 알고리즘 # 1929번 : 소수 구하기

def prime(num):
    if num < 2:
        return False
    
    i = 2
    while i * i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

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

for i in range(m, n + 1):
    if prime(i):
        print(i)

풀이

점점 def로 함수를 정의해서 푸는게 익숙해지고 있어요..!!🙌 (장족의 발전🤣)

​

def로 정의한 함수를 먼저 풀이해보면, prime으로 소수에 대한 변수를 설정하고

그에 대한 인자(argument)로 num 변수를 설정했어요.

​

다음으로 if문으로 1은 소수가 아니므로 걸러주고

(if num <=1 로 코드를 진행해도 괜찮습니다)

​

다음으로 def 함수를 호출할 때마다 i를 2로 계속해서 초기화 하기 위해서 i를 2로 초기화 시켜두고

while문을 사용해서 2의 제곱인 4보다 num가 클 때 if문이 동작하게 코드를 작성했어요.

while문이 True면 if문으로 가서 num % 2 == 0, 즉 num가 짝수인지 판별해서

짝수라면 False를 return하고 i + 1을 더해주고 다음으로 넘어가요.

​

반대로 while문에서 바로 빠져나오고 False가 아닌 True를 return하게 되면

맨 마지막 for문에서 if문의 조건인 prime(i)가 True가 되므로 if문을 실행해서

i를 출력하면서 풀이 끄--읏!

​

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏

wook2124/Algorithm-Test

최종 소스코드