[백준(BOJ)] 1929번 : 소수 구하기 - PYTHON[파이썬]

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

1929번: 소수 구하기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

---

 

⊙ 문제 접근 과정

 

1. 범위를 입력받는다.
2. 범위 안에서 소수를 에라토스테네스의 체 알고리즘을 통해 찾는다.
3. 찾았다면 값 출력

※주의

  시간 초과를 해결하기 위해 에라토스테네스의 체 범위를 제곱근까지 했다. 그래도 무방하기 때문.

---

 

⊙ 문제 풀이

 

import sys

M, N = map(int, sys.stdin.readline().split()) #입력 받기 (속도 향상)

def isPrime(a): #에라토스테네스의 체
    if(a<2):
        return False
    for i in range(2,int(a**0.5) + 1): #시간 초과를 피하기 위해 제곱근까지만 조사
        if(a%i==0):
            return False
    return True

for i in range(M,N+1): #범위 안에서
    if(isPrime(i)): #소수라면
        print(i) #값 출력

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!