[Python] 코딩 도장 - Largest prime factor

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: Largest prime factor] - Lv.2

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 한다.

예를 들면 13195의 소인수는 5, 7, 13, 29 이다.

600851475143의 소인수 중에서 가장 큰 수를 구하시오.

출처: https://codingdojang.com/scode/450?answer_mode=hide

---

[풀이]

def Largestprimefactor(n):
    i = 2
    a= {}
    while n != 1:
        j=0
        while n % i == 0:
            n = int(n/i)
            j += 1
        if j != 0:
            a[i] = j
        i += 1
    return print(max(a.keys()), a)

Largestprimefactor(600851475143)

6857 {71: 1, 839: 1, 1471: 1, 6857: 1}

전체적인 방법으로 모든 소인수로 n을 나누면 1이 되므로 n이 1이 될 때까지 while문을 사용하였다.

두 번째 while문은 처음엔 2로 나누되 더 이상 2로 나눠지지 않을 때까지 반복하면서 n을 갱신해준다.

이러면 2의 배수 즉, 소수가 아닌 수에 대해선 두 번째 while문은 실행되지 않을 것이다.

다음은 3에 대해 실행 4는 패스, 5는 실행, 6은 패스, 7은 실행 등 소수에 대해서만 작동된다.

---

[추천 풀이]

def Largest_prime(n):
    cnt = 2
    while cnt < n:
        if n % cnt  ==  0:
            Largest_prime(n/cnt)
            return 0
        cnt += 1
    print(n)

Largest_prime(600851475143)

6857.0





0

이 분도 비슷하지만 나와 달리 while을 하나만 사용하고 재귀 방식을 사용하였다.