프로젝트 오일러 #3: 가장 큰 소인수

링크: Project Euler , HackerRank

문제 설명:

주어진 가장 큰 소인수를 찾아야 합니다.

NNN

, 어디

10≤N≤101210\le N\le 10^{12}10≤N≤1012

, 프로젝트 오일러의 경우

NNN

~이다

600851475143600851475143600851475143

.

해결책:

내 전략은 소수 목록을 최대값N까지 미리 계산한 다음 각 목록에서 가장 큰 소인수N를 계산하는 것입니다.

소수는 로만 나누어 떨어지는 수이다.

111

그리고 그 자체. 따라서 숫자가 소수인지 식별하는 간단한 알고리즘은 다음과 같아야 합니다.

def is_prime(num: int) -> bool:
    if num <= 1: return False

    # We need to check divisibility till the square root of N
    # see https://stackoverflow.com/a/5811176/8010366
    till = math.floor(math.sqrt(num)) + 1
    for div in range(2, till):
        if num % div == 0:
            return False
    return True

위의 알고리즘에서 다음보다 작은 모든 숫자로 나누어지는 것을 확인할 필요가 없습니다.

N\sqrt{N}N

. unique factorization theorem에 따르면 모든 수는 소수의 곱으로 나타낼 수 있으므로 위의 알고리즘을 수정하여 자신보다 작은 소수로만 나눌 수 있는지 확인할 수 있습니다. 또한 이러한 방식으로 우리가 계속 원했던 소수 목록을 생성하고 있습니다.

# Calculates prime numbers till
class Prime:
    def __init__(self, till):
        self._till = till
        self._primes = []
        self._calculate_prime()

    def _calculate_prime(self):
        def _is_prime(n):
            # check if its divisible till sqrt of n if not then its a prime number
            check_till = math.floor(math.sqrt(n)) + 1
            for p in self._primes:
                if p > check_till: return True
                if n % p == 0: return False
            return True

        for n in range(2, self._till + 1):
            if _is_prime(n): self._primes.append(n)

    def is_prime(self, num):
        return num in self._primes

    def till(self, num):
        for p in self._primes:
            if p <= num: yield p

이제 실제로 가장 큰 소인수를 찾는 두 번째 부분입니다. 아시다시피 모든 숫자는 소수의 곱으로 나타낼 수 있습니다.

202020년

다음과 같이 정의할 수 있습니다.

22*52^2 * 522*5

. 여기서 우리는 가장 큰 소수 승수(즉,

555

). 그래서 우리는 모든 더 작은 것들을 반복적으로 나눔으로써 가장 큰 소승수를 얻을 수 있습니다. 이 방법으로 더 작은 크기를 선택하여 알고리즘을 최적화합니다.

NNN

더 큰 것 대신에.

def largest_prime_factor(n, primes):
    check_till = math.floor(math.sqrt(n)) + 1
    for p in primes.till(check_till):
        while n % p == 0:
            n //= p

    # p is the last remaining prime number if n is completely divided by it
        if n == 1:
            return p

    # If n in itself is a prime number, it will not be divided by anything
    # In that case we return n
    return n

최종 HackerRank 제출

#!/bin/python3

import sys
import math

class Prime:
    def __init__(self, till):
        self._till = till
        self._primes = []
        self._calculate_prime()

    def _calculate_prime(self):
        def _is_prime(n):
            check_till = math.floor(math.sqrt(n)) + 1
            for p in self._primes:
                if p > check_till: return True
                if n % p == 0: return False
            return True

        for n in range(2, self._till + 1):
            if _is_prime(n): self._primes.append(n)

    def till(self, num):
        for p in self._primes:
            if p <= num: yield p

def largest_prime_factor(n, primes):
    check_till = math.floor(math.sqrt(n)) + 1
    for p in primes.till(check_till):
        while n % p == 0: n //= p
        if n == 1: return p
    return n

primes = Prime(1000001)

t = int(input().strip())
for a0 in range(t):
    print(largest_prime_factor(int(input().strip()), primes))

읽어 주셔서 감사합니다.