URL : https://programmers.co.kr/learn/courses/30/lessons/87389
문제 설명
- 자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.
제한 사항
- 3 ≤ n ≤ 1,000,000
문제 풀이
- 1이 남는수를 구하니까 일단 n에서 1을 뺀 x를 구한다.
- 이후 x가 홀수인가, 짝수인가에 대한 경우의 수가 있다.
- 1) x가 짝수라면 무조건 2가 최소의 수이므로 2를 리턴한다.
- 2) x가 홀수라면 x가 소수 (1과 자기 자신이 아니면 나누어 떨어지지 않는수) 일수 있으므로 소수 검사를 한다.
- 3) 소수가 아니라면 가장 먼저 나누어떨어지는 수 i를 return
- 4) 소수라면 x를 return
- 이때 소수를 검사할때는 2부터 자기 자신의 수 까지가 아닌, 약수의 특성(중간값의 양 옆은 대칭)을 이용하여 루트를 씌운값으로 판별하면 속도가 더 빠르다.
1
2
3
4
5
6
7
8
9
import math
def solution(n):
x = n - 1
if x % 2 == 0:
return 2
for i in range(2, int(math.sqrt(x) + 1)):
if x % i == 0:
return i
return x
1
2
n = 10
solution(n)
1
3
1
2
n = 12
solution(n)
1
11