이 스크립트를 조금 더 빠르게 만드는 방법은 무엇입니까?

for i in xrange(1, 600851475141): 
    if 600851475141 % i == 0: 
    print i

이것은 너무 많은 시간을 소비합니다. 더 빨리 만들 수 있습니까?이 스크립트를 조금 더 빠르게 만드는 방법은 무엇입니까?

출처

2013-03-06 Александр Кривошеев

이 절반 범위에 대해서만 가자 산출? 값/2를 지나면 어떤 구분자도 찾을 수 없을 것입니다. 'xrange (1, 600851475141/2)의 경우 : – ppeterka

홀수 만 확인하십시오. – gefei

2/4/8로 단계를 수행하고 고리. 일컬어 un-rolling. 때로는 속도를 줄지는 모르겠지만 (그런 코드를 유지 보수하는 데 더 많은 노력을 기울여야합니다.) – hakre

모든 제수가 sqrt(N)보다 작 으면 sqrt(N)보다 큰 상수 약수가 있습니다. 따라서 i의 제수는 sqrt(N)보다 작고 은의 상보적인 제수 N//i을 계산하면됩니다.

import math 
N = 600851475141 
divisors = [] 
for i in xrange(1, int(math.sqrt(N))+1): 
    if N % i == 0: 
     divisors.extend(set((i, N//i))) 
for d in sorted(divisors): 
    print(d)

는

1 
3 
11981 
35943 
16716787 
50150361 
200283825047 
600851475141

출처

2013-03-06 11:11:49 unutbu

+1 숫자가 완전한 정사각형이면 제곱근이 두 번 인쇄된다는 것이 유일한 문제입니다. – Volatility

@ 가변성 : 수정 해 주셔서 감사합니다! – unutbu

음, 소수 만 반복하여 더 이상 최적화 할 수 있습니까? n 개의 소수를 미리 준비하는 것은 상대적으로 쉽습니다. 많은 N의 문제를 해결할 필요가 있다면 단지 노력할 가치가 있습니다. 그러나 여러분은'sqrt (N)'에서'log (sqrt (n))'까지 복잡성을 떨어 뜨릴 수 있다고 생각합니다. 아니면 내가 틀렸어? – luk32

이 스크립트를 조금 더 빠르게 만드는 방법은 무엇입니까?

답변

관련 문제