[백준] 1929번: 소수 구하기 - Python

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

 

생각

• M, N을 입력받음
• M부터 N까지 반복문을 돌며 소수 판별
• 소수는 무엇인가 -> 약수를 1과 자기 자신만을 가지는 수
• 하나의 수를 num이라 할 때 2부터 num -1 까지의 수를 눴을 때 나머지가 0이 되는 경우가 있으면 소수가 아님
• 2중 for문을 써야겠다

구현 1 - 시간초과

M, N = map(int, input().split(" "))
result = []

for num in range(M, N+1):
    if num > 2:
       for i in range(2, num):
           if num % i == 0:
                break
           if i == num-1:
                result.append(num)
for i in result:
    print(i)

• 흠 2중 for문은 시간초과가 나오는 것 같다.
• 소수를 한번에 판별 할 수 있는 연산이 있나?

구현2 - 제곱근까지만 검사

M, N = map(int, input().split())

result = []

for num in range(M, N + 1):
    if num > 1:  # 1은 소수가 아니므로 제외
        is_prime = True
        for i in range(2, int(num**0.5) + 1):  # 제곱근까지만 검사
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            result.append(num)

for i in result:
    print(i)

• 약수를 num의 제곱근까지만 검사해도 소수를 판별할 수 있다고 한다
• 생각해보니 num의 제곱근 보다 큰 수로 나누는 것은 의미가 없다.. ㅇㅅㅇ

 

 

마무리

• 소수를 구할 때 제곱근까지만 판별한다는거 예전에 공부 했던 내용인데 오랜만에 접하니 떠오르지 않았다.
• 이제 슬슬 코테 감좀 잡아봐야지