밑의 링크는 CodeUp에서의 문제 링크입니다.
문제는 링크를 통해서 직접 봐주시길 바랍니다.
소수 판별
입력으로 주어진 수가 소수이면 "prime"을 출력, 소수가 아니면 "not prime"을 출력한다.
codeup.kr
주의해야 할 점
1. readline과 int나 float를 사용하는 입력 방식
readline을 사용해서 입력할 때는 맨 끝에 \n이 붙어서 입력됩니다.
하지만, 입력한 값을 int나 float으로 처리해 정수, 실수형으로 만들어 줄 때는
굳이 \n을 떼기 위해 rstrip을 사용할 필요가 없습니다.
숫자 형태를 만들어줄 때 자동으로 사라집니다.
num = int(sys.stdin.readline())
2. 소수 판별
어떤 한 숫자가 소수인지 아닌지를 판별할 때,
어떻게 짜야 제일 효율적인 알고리즘일지에 대한 글들이 많습니다.
해당 숫자까지, 해당 숫자의 절반까지, 해당 숫자의 제곱근까지 확인하는 방법
혹은 또 다른 다양한 방법들 중에서
어떤 것이 제일 효율적일지 생각해보고 검색도 해서 열심히 공부해봅시다.
예제 설명
1. 첫 번째 예제
- 입력
7
- 출력
prime
- 설명
2 이상인 입력한 자연수는 7입니다.
7의 약수는 1, 7이므로 1과 자기 자신 뿐입니다. 즉, 7은 소수입니다.
따라서 문자열 prime을 출력합니다.
생각한 풀이 과정
2 이상인 자연수를 입력합니다.
입력한 자연수가 소수인지를 판별하기 위해
2부터 입력한 자연수의 제곱근 이하의 자연수까지 나누어 봐야 합니다.
저 제곱근 이하의 자연수에 1을 더한 값을 구하고 limit 변수에 저장합니다.
2부터 limit - 1 값인 입력한 자연수의 제곱근 이하의 자연수까지 반복해봅니다.
입력한 자연수를 현재 숫자로 나누었을 때 나머지가 0이라면,
현재 숫자도 입력한 자연수의 약수이므로 현재 숫자는 소수가 아닙니다.
따라서 문자열 not prime을 출력하고 반복문을 탈출합니다.
입력한 자연수를 2부터 limit - 1까지 나누었을 때 나머지가 0인 경우가 없다면,
입력한 자연수는 소수이므로 문자열 prime을 출력합니다.
제출한 파이썬 코드
# readline을 사용하기 위해 import합니다.
from sys import stdin
# 2 이상의 자연수를 입력합니다.
# int형으로 변환합니다.
num = int(stdin.readline())
# 소수를 판별하기 위해 입력한 자연수를 2부터 입력한 자연수의 제곱근 이하의 자연수까지 나누어 봐야하므로
# 입력한 자연수의 제곱근을 구해 int형으로 변환하고 1을 더한 제한값을 구해 변수에 저장합니다.
limit = int(num ** 0.5) + 1
# 2부터 입력한 자연수의 제곱근 이하의 자연수까지 반복해봅니다.
for divisor in range(2, limit):
# 입력한 자연수를 현재 숫자로 나누었을 때 나머지가 0이라면
if num % divisor == 0:
# 입력한 자연수는 소수가 아니므로 문자열 not prime을 출력합니다.
print('not prime')
# 소수인지 아닌지 판별했으므로 반복문을 탈출합니다.
break
# 입력한 자연수를 2부터 limit까지 나누었을 때 나머지가 0인 경우가 없다면
else:
# 입력한 자연수는 소수이므로 문자열 prime을 출력합니다.
print('prime')
제출 결과
느낀 점
예전에 어떤 숫자가 소수인지 아닌지를 판별하는 알고리즘 문제들을 풀었을 때
다른 공부 자료를 읽지 않고 그냥 풀었을 때의 저는
해당 숫자의 절반까지가 제일 좋은 알고리즘인 줄 알았지만,
해당 숫자의 제곱근까지만 확인하면 더 빠른 시간 복잡도가 된다는 것을 알게 된 지금은
소수 판별을 해야 되는 문제를 만나면 이 알고리즘으로 열심히 풀고 있습니다.
댓글