[파이썬] 백준 1929 소수 구하기, 소수 판별법

백준 1929 문제풀이

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

백준 1929

풀이

• 소수란
  • 1과 자기 자신으로밖에 나누어 떨어지지 않고, 자기 자신의 곱셈의 역수가 없는 수
• 소수 예시
  • 10
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 2,3,5,7
• 알고리즘
  • 어떤 수 N 이하의 수로 N을 나눠서 한 번이라도 나누어 떨어지면 합성수, 아니면 소수
    여기서 N 이하는 N의 양의 제곱근 이하의 수로 판별할 수 있는 것이 key point
    → math 모듈의 sqrt() 함수 활용

아래와 같이 주어진 입력값 기반의 반복문으로 풀면 시간초과 발생

import sys
var = sys.stdin.readline().rstrip().split(" ")
rtn = ""
for i in range(int(var[0]), int(var[1])+1):
    pnumYN = ""
    cnt = 2
    while cnt <= i:
        if (i!=cnt and i%cnt == 0):            
            break
        elif (cnt == i):
            rtn += str(i)+"\n"
        cnt += 1
print(rtn.rstrip())

 

key point 조건을 적용하여 구현

• N 이하는 N의 양의 제곱근 이하의 수로 판별
• math 모듈의 sqrt() 함수 사용

#어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한 번이라도 나누어 떨어지면 합성수, 아니면 소수라고 판정
import sys
import math
M, N = sys.stdin.readline().rstrip().split(" ")

def primeNumYN(num):    
    if num == 1:
        return "N"
    if num == 2:
        return "Y"
    if (num % 2 == 0):
        return "N"
    if (num > 2):
		#num 의 제곱근 이하까지 반복 (math.sqrt() 사용)
        for i in range(3, math.trunc(math.sqrt(float(num)))+1, 2):
            if (num % i == 0):
                return "N"
        return "Y"

for j in range(int(M), int(N)+1):
    if (primeNumYN(j) == "Y"):
        print(j)
"""
3 16
3
5
7
11
13
"""

 

☞ 파이썬 자습서 참고 자료

https://docs.python.org/ko/3/library/math.html#math.sqrt

math — Mathematical functions

☞ 소수 판별법 참고자료

소수판별법 - 위키백과, 우리 모두의 백과사전