백준 - 11653 (python)

 

 

첫 번째 풀이

 

 

def find_primes(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes


N = int(input())
primes = find_primes(N)
index = 0
while N != 1:
    if N % primes[index] == 0:
        print(primes[index])
        N //= primes[index]
    else:
        index += 1

 

미리 n까지의 소수를 담은 배열을 생성하고

반복문을 통해 소인수 분해를 하는 코드를 작성했다.

결과는 시간초과

 

찾아보던 중 에라스토네스의 체 라는 알고리즘을 발견하고 코드를 수정했다.

 

def find_primes(n):
    primes = []
    sieve = [True] * (n+1)  # True로 된 초기 배열 생성
    for p in range(2, n+1): 
        if sieve[p]:  
            primes.append(p)
             # 소수를 찾았으면 해당 소수의 제곱부터 배수까지 모두 소수가 아님을 표시
            for i in range(p*p, n+1, p): 
                sieve[i] = False
    return primes

N = int(input())
primes = find_primes(N)
index = 0
while N != 1:
    if N % primes[index] == 0:
        print(primes[index])
        N //= primes[index]
    else:
        index += 1

 

2부터 N까지 반복문을 돌려 소수를 담은 배열을 찾는것보다 훨씬 효율적인 알고리즘이었다.

 

라고 생각했는데 더 효율적인 코드가 있다..

 

N=int(input())
for i in range(2,int(N**(0.5))+2):
    while N%i==0:
        print(i)
        N//=i
if N!=1: print(N)

 

 

수학적 지식이 필요한부분