1일 N알고리즘 - #22

문제

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

1929번: 소수 구하기

문제는 위 사이트를 참고해주세요.

 

---

풀이

def findPrime(num):
    if num == 1:
        return False
    n = int(num ** 0.5)

    for k in range(2, n+1):
        if num % k == 0:
            return False
    return True

m, n = map(int, input().split())
for i in range(m, n+1):
    if findPrime(i):
        print(i)

 

먼저 수가 소수인지 아닌지 판별하는 함수를 만들어줍니다.

1은 소수가 아니기 때문에 1일 들어올 경우 false를 리턴합니다.

 

그렇지 않으면 들어온 값에 루트를 씌우고 그 값을 int형으로 n에 저장합니다.

ex)) num = 4 --> n = 2, num = 5 --> n=2, num = 121 --> n=11

 

그리고 2부터 시작하는 for문을 돌려서 num % k 값이 0인 경우 false

아니면 true를 리턴합니다.

 

함수를 끝내고 m,n을 입력받아 for문을 돌려 소수를 판단합니다.

 

 

전에 했던 코드로 진행하면 시간초과가 나와서 찾아보니

https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/

소수 구하기 (에라토스테네스의 체)

이런 알고리즘이 있었습니다.

에라토스테네스의 체를 이용해서 문제를 풀어보세요.

 

---

결과

결과 화면