백준 11653번 소인수분해

문제 링크:https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

 

간단 회고:

	O	X
내가 직접 풀었나?	✔
다른 사람 풀이를 참고 하였나?		✔
어려웠나?		✔
푸는데 오래걸렸나?		✔

✅✔

 

맞았습니다!!

207948

996

PyPy3 / 수정

818

소수 찾기 부분을 제외하면 로직자체는 금방 구현했다. 소수찾기는 이미 구현했던 함수들을 따왔다. 이게 핵심인 알고리즘 문제는 아니라고 판단했다.

 

단순히 소수들을 모두 탐색하며 계속해서 나누어보는 식의 브루트포스 알고리즘 방식을 적용했다.

덕분에 시간은 엄청 걸린다... 이를 발전시킬 방향을 찾기위해 나중에 다른 사람들의 풀이를 참고해볼 생각이다.

 

 

내 풀이:

 

#소인수분해

n = int(input().rstrip())

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def find_all_primes(n):
    sieve = [False, False] + [True] * (n - 1)
    primes = []
    for i in range(2, n + 1):
        if sieve[i]:
            primes.append(i)
            for j in range(i * 2, n + 1, i):
                sieve[j] = False
    return primes


#exception handling
if n == 1:
    exit()
elif is_prime(n):
    print(n)
    exit()

#n**0.5 +1까지의 모든 소수 찾기
prime_list = find_all_primes( n//2 + 1 )

#열심히 찾기
for i in prime_list:
    while True:
        if n % i == 0:
            n = n // i
            print(i)
        else:
            break
    if n == 1:
        break

 

 

 

 

참고한 타 풀이 및 출처(있다면)

 

bye