[백준] 11653 소인수분해

www.acmicpc.net/problem/11653

import sys
input = sys.stdin.readline
n = int(input())

i = 2
while n > 1:
    if n % i == 0:
        n //= i
        print(i)
    else:    
        i += 1

 

처음에 소수인지 판별하고 몇번 나눠지는지 확인을 했다.

수가 큰 경우에는 소수 판별하는 것부터 오래걸려서 시간을 초과했다.

시간이 오래걸리긴 했지만 무사통과한 코드이다.

아래는 9,000,000 부터 10,000,000 사이에서 결과값이 나오는 시간이 0.5sec 이상인 경우에만 체크한것이다.

9000011: 0.6425809860229492sec
9000041: 0.6375772953033447sec
9000049: 0.6375768184661865sec
9000059: 0.6375763416290283sec
9000067: 0.6395785808563232sec
9000119: 0.6375765800476074sec
9000127: 0.6365756988525391sec
9000143: 0.6395783424377441sec
9000163: 0.6385774612426758sec
9000193: 0.6375763416290283sec
9000203: 0.6415801048278809sec
9000209: 0.6395783424377441sec
9000217: 0.6395783424377441sec
9000223: 0.6355741024017334sec
9000253: 0.6395790576934814sec
9000269: 0.6375765800476074sec
9000283: 0.6375765800476074sec
9000289: 0.6365756988525391sec
9000317: 0.63657546043396sec
9000331: 0.6365759372711182sec
9000349: 0.6385772228240967sec
9000377: 0.6365756988525391sec
9000379: 0.6375768184661865sec
9000403: 0.6405797004699707sec
9000427: 0.6375768184661865sec
9000451: 0.6405792236328125sec
9000461: 0.6375758647918701sec
9000473: 0.6375765800476074sec
9000487: 0.6375765800476074sec
9000499: 0.63657546043396sec
9000517: 0.6385774612426758sec
9000569: 0.6395783424377441sec
9000577: 0.6395783424377441sec
9000601: 0.6395776271820068sec
9000637: 0.6385776996612549sec
9000683: 0.6405794620513916sec
9000703: 0.6355745792388916sec
9000709: 0.6375761032104492sec
9000721: 0.6395783424377441sec
9000743: 0.6375765800476074sec
9000767: 0.6375765800476074sec
9000773: 0.6405794620513916sec
9000779: 0.6385774612426758sec
9000781: 0.6375763416290283sec
9000787: 0.6405792236328125sec
9000791: 0.6365761756896973sec
9000793: 0.6375761032104492sec
9000809: 0.6365756988525391sec
9000821: 0.6365756988525391sec
9000839: 0.63657546043396sec
9000841: 0.6375765800476074sec
9000877: 0.6355750560760498sec
9000899: 0.6375768184661865sec
9000907: 0.6375768184661865sec
9000913: 0.6405794620513916sec
9000931: 0.6375768184661865sec
9000961: 0.6405792236328125sec
9000983: 0.6375765800476074sec
9000989: 0.6375765800476074sec
9000997: 0.6365756988525391sec
9001001: 0.6455838680267334sec
9001033: 0.6365756988525391sec
9001039: 0.6365756988525391sec
9001063: 0.6375768184661865sec
9001093: 0.6365759372711182sec
9001121: 0.6395792961120605sec
9001163: 0.6405792236328125sec
9001169: 0.6405797004699707sec
9001171: 0.6375763416290283sec
9001189: 0.6355748176574707sec
9001199: 0.6355748176574707sec
9001219: 0.6365756988525391sec
9001229: 0.6395783424377441sec
9001243: 0.6405792236328125sec
9001259: 0.6385774612426758sec
9001277: 0.6375768184661865sec
9001283: 0.6375761032104492sec
9001301: 0.6365759372711182sec
9001337: 0.6405794620513916sec
9001351: 0.6365756988525391sec
9001387: 0.6365761756896973sec
9001417: 0.6375763416290283sec
9001429: 0.6385774612426758sec
9001463: 0.63657546043396sec
9001481: 0.6375765800476074sec
9001493: 0.64158034324646sec

 

---

n = int(input())
i = 2
while i*i <= n:
	if n % i == 0:
		n /= i
		print(i)
	else:
		i += 1
if n != 1:
	print(int(n))

아래는 큰 차이없는 코드인데 시간상 엄청 빠르길래 가져왔다

우선, while의 조건이 i*i<n 을 볼 수 있다.

i가 n의 제곱근 이상으로 올라가면 이미 소인수로 나누어졌거나, 소수인 경우밖에 없으므로 판단을 할 필요가 없다.

그리고 반복문이 끝난 이후 1이 아닌 경우는 소수이므로 바로 출력을 해준다.

 

 

더 공부해야겠다...