import time
from math import *
N = 145234533
t = time.time()
if N == 1 :
print('')
for i in range(2, N+1):
if N % i == 0:
while N % i == 0:
N /= i
print(i)
print("걸린시간:",time.time()-t)
23초 정도 나온다
근데 같은 숫자로 N의 루트까지만 돌리면 훨씬 빠름
import time
from math import *
N = 145234533
t = time.time()
for i in range(2, int(sqrt(N))+1):
if N % i == 0:
while N % i == 0:
N /= i
print(i)
if N == 1 :
print('')
else:
print(int(N))
print("걸린시간:",time.time()-t)
엄청 차이남
그리고 생각해보면 N이 계속 나누어지고 있는데
처음의 N만큼 가야할 이유도 없음..
중간에 나누어진 N의 루트 까지만 구해도 됨
그래서 나누어질때마다 범위 줄어들도록 while문으로 바꿔주면...
import time
from math import *
N = 14523453342223532
t = time.time()
for i in range(2, int(sqrt(N))+1):
if N % i == 0:
while N % i == 0:
N /= i
print(i)
if N == 1 :
print('')
else:
print(int(N))
print("걸린시간:",time.time()-t)
import time
from math import *
N = 14523453342223532
t = time.time()
i = 2
K = int(sqrt(N))+1
while i < K:
if N % i == 0:
while N % i == 0:
N /= i
print(i)
K = int(sqrt(N))+1
i += 1
if N == 1 :
print('')
else:
print(int(N))
print("걸린시간:",time.time()-t)
(숫자 더 크게 바꿨음)
인수가 많을수록 효율적이라고 생각함
소인수도 사람이야 사람!!
근데 코드가 저러면 sqrt(N)을 계속 계산하네; 다른 변수에다가 넣어놓고 제일 안쪽 while문 안에서 업데이트 해야 나누어 질때마다 업데이트 할듯
박궜다