相关疑难解决方法(0)

计算给定数量的除数的最佳算法(性能方面)是什么？

如果您能提供伪代码或链接到一些示例,那将会很棒.

编辑:所有答案都非常有帮助,谢谢.我正在实施Atkin的Sieve,然后我将使用类似于Jonathan Leffler所说的东西.Justin Bozonier发布的链接提供了我想要的更多信息.

我一直试图通过Project Euler工作,并注意到一些问题要求你确定一个素数作为其中的一部分.

1. 我知道我可以将x除以2,3,4,5,...,X的平方根,如果我到达平方根,我可以(安全地)假设该数字是素数.不幸的是,这个解决方案似乎非常笨重.

2. 我已经研究了如何确定数字是否为素数的更好的算法,但是快速混淆.

是否有一个简单的算法可以确定X是否是素数,而不是混淆一个凡人的程序员？

非常感谢!

我目前正在解决一个数学问题,其中我需要计算减少的适当分数的数量,分子和分母都超过1000000(10 ^ 6).

我有适用于小数字的代码; 给出的示例(值= 8)给出正确的(给定的)答案21.

但是由于我不知道的原因,这个代码似乎对大数字来说非常慢.我在SO上阅读了大量类似的问题,但找不到任何有用的东西.我仔细研究了这个和这个,但这并没有真正帮助我.我的代码以可接受的速度运行,直到1000,然后它变得超级超慢.

import math

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    sqr = int(math.sqrt(n)) + 1
    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True

def get_divisors(n):
    liste = [1]
    if n % 2 == 0:
        liste.append(2)
    for divisor in range(3, n+1):
        if n % divisor == 0:
            liste.append(divisor)
    return liste …

我需要计算数字 N 的除数总数（不关心除数的值是多少），并对所有这些数字 N 在 40-80 次运算内完成。我该怎么做？这不是一个家庭作业问题。我尝试了Pollard 的 Rho算法，但即使这样对于我的目的来说也太慢了。这是我的 python 代码。如果可能的话，我该如何提高其性能？

def is_prime(n):    
    if n < 2:
        return False
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,
         43,47,53,59,61,67,71,73,79,83,89,97]
    def is_spsp(n, a):
        d, s = n-1, 0
        while d%2 == 0:
            d /= 2; s += 1
        t = pow(int(a),int(d),int(n))
        if t == 1:
            return True
        while s > 0:
            if t == n-1:
                return True
            t = (t*t) % n
            s -= 1
        return False
    if n in ps: return True
    for p …

我正在尝试解决Euler项目上的第12个问题。我可以计算出将近4分钟内有500个除数的数字。我怎样才能使其更快？这是尝试；

import time

def main():
    memo={0:0,1:1}
    i=2
    n=200
    while(1):
        if len(getD(getT(i)))>n:
            break
        i+=1
    print(getT(i))

#returns the nth triangle number
def getT(n):
    if not n in memo:
        memo[n]=n+getT(n-1)
    return memo[n]

#returns the list of the divisors
def getD(n):
    divisors=[n]
    for i in xrange(1,int((n/2)+1)):
        if (n/float(i))%1==0:
            divisors.append(i)
    return divisors

startTime=time.time()
main()
print(time.time()-startTime)

获取给定整数的整个因子对列表的最简单方法是什么？

例如:f(20)会回来[(1,20), (2,10), (4,5)].

我正在尝试解决涉及打印给定数量的所有除数的乘积的问题.测试用例的数量是1 <= t <= 300000,数字本身的范围可以从1 <= n <= 500000

我写了下面的代码,但它总是超过2秒的时间限制.有没有办法加快代码？

from math import sqrt

def divisorsProduct(n):
    ProductOfDivisors=1

    for i in range(2,int(round(sqrt(n)))+1):
        if n%i==0: 
            ProductOfDivisors*=i

            if n/i != i:
                ProductOfDivisors*=(n/i)    

    if ProductOfDivisors <= 9999:
        print ProductOfDivisors
    else:
        result = str(ProductOfDivisors)
        print result[len(result)-4:] 

T = int(raw_input())

for i in range(1,T+1):
    num = int(raw_input())
    divisorsProduct(num)

谢谢.