[2312] 수 복원하기 in python

 

수 복원하기 문제는

소수를 통해 소인수 분해를 진행해야 했다.

 

소수를 구할땐

에라토스테네스의 체를 이용하면

빠른 시간 내에 소수를 구할 수 있다.

 

문제에서 주어진 최대의 수만큼 리스트를 생성하고

소수를 모아둔 리스트를 prime에 넣는다.

-> 소수를 구하는 과정을 1번만 진행하기 위함.

 

 

소인수를 구할 때 소수를 이용한다.

만약 주어진 수가 6이라고 치면

6을 소인수 분해하면 2 1 , 3 1 이렇게 답이 나온다.

즉 2 x 3 = 6,

 

12를 소인수 분해하면 2 2 , 3 1

즉 (2x2) x (3x1) = 12

 

12이하인 소수들 가지고만 판별을 진행한다.

1) 소수(i) 2, num = 12

12 % 2 = 0일 경우 2를 인자로 가지고 있다.

cnt+=1

num에는 2를 나눠야한다. 

따라서 num = num//2

 

위 과정을 반복하다가

num % i 의 값이 0이 아닐 경우

answer 리스트에 현재의 i값과 cnt 값을 리스트 형식으로

넣어주면 된다.

 

위 과정을 반복하면 끝!

 

(실행 시간은 144ms)

 

t = int(input())
nums = [int(input()) for _ in range(t)]
temp = [1 for _ in range(100001)]
prime = []

for i in range(2, 100001):
    if temp[i]:
        prime.append(i)
        for j in range(i * 2, 100001, i):
            if j > 100000:
                break
            temp[j] = 0

for num in nums:
    answer = []
    for i in prime:
        if i > num:
            break
        if num % i == 0:
            cnt = 0
            while num % i == 0:
                cnt += 1
                num = num // i
            answer.append([i, cnt])
    for a, b in answer:
        print(a, b)

---

 

 

import sys
import math
I = sys.stdin.readline

for i in range(int(I())):
    n = int(I())
    i = 2
    while i*i <= n:
        cnt = 0
        if n%i == 0:
            while (n%i == 0):
                n = n//i
                cnt += 1
            print(i, cnt)
        i += 1
    if n > 1:
        print(n, 1)

 

해당 코드는 실행시간이 60ms 내외인 코드!

 

while i * i <= n:
    cnt = 0
    print("i =", i, "n =", n)
    if n % i == 0:
        while n % i == 0:
            n = n // i
            cnt += 1
            print("i=",i)
        print(i, cnt)
    i += 1
if n > 1:
    print(n, 1)