[백준 알고리즘/Python3] 11653 소인수분해

문제이해

소인수분해라면 어떠한 수가 주어졌을 때 소수로 나눌 수 없을 때 까지 나눈 값들을 소인수분해라고 하지 않나?

 

예시이다.

 

1. 그러면 우리는 일단 소수를 구하고

2. 소수의 가장 작은 것 부터

3. 적어준 값에 나눠봐서

4. 몪이 정수형태로 나오지 않을 때까지

5. 나누면 되지 않을까?

 

 

num = int(input())

sosu_nums = []
for i in range(1,num+1):
    count = 0
    if(i > 1):
        for j in range(2, i):
            #소수가 아님
            if(i % j == 0):
                count +=1
                
        if(count == 0):
            sosu_nums.append(i)
print(sosu_nums)

1번을 수행한 것이다. 

 

값을 넣으면 sosu_nums에 소수가 쌓인다. 

2부터 쌓인다.

 

그렇다면 소수 가장 작은 것은 sosu_nums 첫번째에 있을 것입니다.

 

만약 주어진 수의 나머지가 0이 아니라면  그건 소인수 분해가 끝이 났거나, 다른 소수로 나눠봐야 합니다.

 

값을 나눴어 -> 몫이 정수가 나오거나 (나머지가 0)

                -> 몫이 소수점으로 나오거나 (나머지가 0이 아님)

 

 

코드를 봐보면 

num = int(input())

sosu_nums = []
for i in range(1,num+1):
    count = 0
    if(i > 1):
        for j in range(2, i):
            #소수가 아님
            if(i % j == 0):
                count +=1
                
        if(count == 0):
            sosu_nums.append(i)
print(sosu_nums)

t = 0
# num이 나눠진다면 다시 num을 처음부터 시작한다.
while((t) < len(sosu_nums)):
    #나머지
    na = num % sosu_nums[t]
    if(na != 0):
        t += 1
        continue
    #print("num: " ,num)
    print(sosu_nums[t])
    #몫
    num = int(num) / sosu_nums[t]

이렇게 쓰니 시간 초과가 납니다.

더 좋은 방법이 있는거 보다 더 좋은 방법이 있는거 같습니다.

 

 

주어진 수의 소수를 찾고 

그 수에다가 모든 소수를 나누려니  => 시간 초과가 떳습니다.

에라토스테네스의 체의 원리로 소수를 찾아봐도 시간초과가 => 떴습니다.

 

다른 방법을 찾아보다가 

주어진 수를 2부터 나누면서 while문을 돌려보면 어떨까 생각했습니다.

 

어처피 2에서 못나누면 => 4에서도 못나누고 => 6에서도 못나누고...

3에서 못나누면 => 6에서도 못나누고 => 9에서도 못나누고 ...

 

 

즉. 주어진 수를 2부터 나눠봐서 주어진 수를 줄여나가는게 답인거 같습니다.

num = int(input())

t = 2
while(num >= 0):
    if(num == 1):
        break
    
    #들어온 값이 2부터 나눠진다면
    if((num) % t == 0):
        print(t)
        num = num // t
        t = 2
        continue
    t += 1