[백준] 1929번 : 소수 구하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1929번: 소수 구하기

 

1. 문제 설명

2. 풀이과정

1. sys.stdin.readline() 함수를 사용하여 입력을 받기 위해 sys 모듈을 불러온다. import sys
2. 소수를 구할 범위의 수를 입력받는다. M, N = map(int, sys.stdin.readline().split())
3. 함수를 구현하여 문제를 해결한다. def Func(num)
4. 소수는 1과 자기 자신만 약수로 갖는 수를 말한다. 따라서 어떤 수를 제곱하였을 때 그 수가 소수를 판별할 수보다 크면 어떤 수보다 작은 수 중에서 나누었을 때 나누어 떨어져야 소수가 된다. 해당 풀이 방법은 계속 시간 초과가 나는 코드를 최소한의 반복으로 작성하기 위한 방법이다.
5. 2부터 소수를 판별할 수의 정수 제곱수까지 반복한다. for i in range(2, int(num ** 0.5) + 1)
6. 만약 소수를 판별할 수를 나누었을 때 나누어 떨어지면 if (num % i == 0)
7. 해당 수는 소수가 아니므로 False를 반환한다. return False
8. 반복이 종료되어도 False를 반환하지 않았다면 해당 수는 소수이므로 True를 반환한다. return True
9. 입력받은 두 정수 사이의 값 중 모든 소수를 찾아야 하므로 두 정수 사이의 값이 하나씩 추출되도록 반복문을 작성한다. for i in range(M, N + 1)
10. 만약 추출된 수가 1이 아니고 소수를 판별하는 함수를 사용했을 때 결과가 True이면 if (i != 1) and (Func(i))
11. 추출된 수는 소수이므로 출력한다. print(i)

반응형

3. 소스코드

import sys

M, N = map(int, sys.stdin.readline().split())

def Func(num):
    for i in range(2, int(num ** (1/2)) + 1):
        if (num % i == 0):
            return False
    return True

for i in range(M, N + 1):
    if (i != 1) and (Func(i)):
        print(i)