Posts 나머가 1이 되는 수 찾기 [Python]
Post
Cancel

나머가 1이 되는 수 찾기 [Python]

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
This post is licensed under CC BY 4.0 by the author.

n^2 배열 자르기 [Python]

없는 숫자 더하기[Python]

Comments powered by Disqus.