백준 11653 문제 풀이 python

🐒 소인수분해

https://www.acmicpc.net/problem/11653

✍ 나의 풀이

n = int(input())

count = 2
while n != 1:
    if n % count == 0:
        print(count)
        n //= count
    else:
        count += 1

정수 n을 소인수분해하는 문제다.
소인수분해를 중학생떄 배웠던거 같은데 정확히 기억은 안난다.
그냥 주어진 수를 가장 작은수의 곱들로 나타내는 정도로 이해하고 풀었다.

문제에 정답기록이 있어서 뭔가했는데

전에 인터넷 보다가 눈에 띄는 문제가 있어서 풀었던 적이 있었는데
이 문제였던가보다.

a = int(input())

x = 2 

if a == 1 :
    pass
else:
    while True:
        if a / x == 1.0:
            print(x)
            break
        elif a % x == 0:
            a = a // x
            print(x)
            continue
        if a % 2 != 0:
            x += 1
            continue
        else:
            x += 2
            continue

13일전의 내가 작성한 코드는 이랬다. 다소 복잡한 느낌이 든다 😂

---

🧠 문제 이해

소인수분해는 합성수를 소수들의 곱으로 나타내는 것을 말한다고한다.

일단 나의 코드로도 문제가 풀리긴했는데
나의 코드는 n을 count로 나누어 떨어지는지 확인하고 그렇다면 count를 출력하고 변수 n에 n을 count로 나눈값을 저장했다.

근데 소수를 구하는 문제이니 에라토스테네스의 체같은 방법으로 n까지의 소수 목록을 구하고 소인수를 구하면 시간이 많이 줄어들 것으로 기대한다.

---

다른 답안

이후에 다른 답안을 찾아보기 위해 일단 에라토스테네스의 체를 이용해서 코드를 짜보았다.

n = int(input())

arr = [True for i in range(n+1)]

for i in range(2,n+1):
    if arr[i]:
        for j in range(i+i, n+1, i):
            arr[j] = False

for i in range(2,n+1):
    if arr[i]:
        while n % i == 0:
            print(i)
            n //= i
    if n == 1:
        break

이렇게 하니 시간 초과가 발생했다.

분명 시간을 줄이려 쓰는 알고리즘인데..?

아마 내가 알고리즘을 완전히 이해못하고 불필요한 처리를 하고있는 부분이 있는 것 같다.

궁금해서 백준 질문게시판을 뒤져보니 다음 글을 발겼했다.

https://www.acmicpc.net/board/view/75684

본 문제에서는 에라토스테네스의 체 말고 그냥 소수판별 알고리즘이 빠르다는 것이다.

그래서 소수 판별 알고리즘을 이용해 보았는데

n = int(input())

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

정말 시간이 많이 줄었다!

이런것 보면 신기하다
같은 결과를 출력하지만 알고리즘에 따라 처리시간이 천차만별이니.