如何在代码中实现除数函数？

Question

整体问题：欧拉项目12 - 第一个三角形数值超过五百个因数是多少？

关注的问题：除数功能

语言：Python的

说明：我使用的功能是蛮力并把它带到该程序的时间去寻找比x增加更多的除数的数几乎每指数10或20个数字高。我需要达到500或更多的因子。我已经发现，除数函数就是阻止程序的东西。我所做的研究使我得到除数函数，特别是除数函数，它应该是一个函数，它将计算任何整数的所有除数。我看过的每一页似乎都是针对数学专业，而我只有高中数学。尽管我遇到了一些提到关于素数和阿特金斯筛的页面，但我无法在素数之间建立联系，找到所有整数的除数，也没有在网上找到任何关于它的内容。

主要问题：可能有人解释如何编写除法器功能，甚至提供样品？当我用代码来看待数学概念时，数学概念对我更有意义。非常感谢。

蛮力除数功能：

def countdiv(a): 
    count = 0 
    for i in range(1,(a/2)+1): 
     if a % i == 0: 
      count += 1 
    return count + 1 # +1 to account for number itself as a divisor 

Answer 1

如果您需要暴力破解功能来计算除数（也称为头（n））的数量

这里是什么样子

def tau(n): 
     sqroot,t = int(n**0.5),0 
     for factor in range(1,sqroot+1): 
       if n % factor == 0: 
         t += 2 # both factor and N/factor 
     if sqroot*sqroot == n: t = t - 1 # if sqroot is a factor then we counted it twice, so subtract 1 
     return t 

第二种方法是一个分解n成其首要因素（及其指数）。

tau(n) = (e1+1)(e2+1)....(em+1)其中n = p1^e1 * p2^e2 .... pm^em和p1,p2..pm are primes

更多信息here

第三种方法和更容易理解仅仅是用筛计算tau。

def sieve(N): 
     t = [0]*(N+1) 
     for factor in range(1,N+1): 
       for multiple in range(factor,N+1,factor): 
         t[multiple]+=1 
     return t[1:] 

这是它在行动，在ideone

Answer 2

当搜索的n除数你从来没有寻找超越平方根数n的。每当找到小于sqrt(n)的除数时，只有一个大于根的匹配除数，所以您可以将count加2（如果找到除数d的n，则n/d将是对应的）。

小心平方数，但。 :)当然，根将是一个不算两次的除数。

Answer 3

我在，你只需要搜索最多数量的平方根这里提交的其他两个答案一致。然而，我有一件事需要补充。所提供的解决方案将在合理的时间内为您提供正确的答案。但是当问题开始变得越来越困难时，你需要一个更强大的功能。

看看Euler's Totient function。虽然它只是间接地适用于此，但它在后面的问题中非常有用。另一个相关的概念是Prime Factorization。

改进算法的快速方法是找到数字的素数因式分解。在维基百科的文章中，他们用36作为例子，其素数因子分解为2^2 * 3^2。因此，知道这一点后，可以使用组合函数来查找36个因子的数量。这样，您就不会计算每个因子，再加上您在完成之前只需检查因子2和3。

Answer 4

如果你要解决项目欧拉问题，你需要一些处理质数和整数分解的函数。这里是我的谦虚图书馆，它提供了primes(n),is_prime(n)和factors(n);重点是简单，清晰和简洁的速度为代价，虽然这些功能应为项目欧拉足够：

def primes(n): 
    """ 
     list of primes not exceeding n in ascending 
     order; assumes n is an integer greater than 
     1; uses Sieve of Eratosthenes 
    """ 
    m = (n-1) // 2 
    b = [True] * m 
    i, p, ps = 0, 3, [2] 
    while p*p < n: 
     if b[i]: 
      ps.append(p) 
      j = 2*i*i + 6*i + 3 
      while j < m: 
       b[j] = False 
       j = j + 2*i + 3 
     i += 1; p += 2 
    while i < m: 
     if b[i]: 
      ps.append(p) 
     i += 1; p += 2 
    return ps 

def is_prime(n): 
    """ 
     False if n is provably composite, else 
     True if n is probably prime; assumes n 
     is an integer greater than 1; uses 
     Miller-Rabin test on prime bases < 100 
    """ 
    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 
     if pow(a,d,n) == 1: 
      return True 
     for r in xrange(s): 
      if pow(a, d*pow(2,r), n) == n-1: 
       return True 
     return False 
    if n in ps: return True 
    for p in ps: 
     if not is_spsp(n,p): 
      return False 
    return True 

def factors(n): 
    """ 
     list of prime factors of n in ascending 
     order; assumes n is an integer, may be 
     positive, zero or negative; uses Pollard's 
     rho algorithm with Floyd's cycle finder 
    """ 
    def gcd(a,b): 
     while b: a, b = b, a%b 
     return abs(a) 
    def facts(n,c,fs): 
     f = lambda(x): (x*x+c) % n 
     if is_prime(n): return fs+[n] 
     t, h, d = 2, 2, 1 
     while d == 1: 
      t = f(t); h = f(f(h)) 
      d = gcd(t-h, n) 
     if d == n: 
      return facts(n, c+1, fs) 
     if is_prime(d): 
      return facts(n//d, c+1, fs+[d]) 
     return facts(n, c+1, fs) 
    if -1 <= n <= 1: return [n] 
    if n < -1: return [-1] + factors(-n) 
    fs = [] 
    while n%2 == 0: 
     n = n//2; fs = fs+[2] 
    if n == 1: return fs 
    return sorted(facts(n,1,fs)) 

一旦你知道如何因素的数字，很容易计算除数的数。考虑76576500 = 2^2 * 3^2 * 5^3 * 7^1 * 11^1 * 13^1 * 17^1。忽略基数并查看指数，它们分别是2,2,3,1,1,1和1.给每个指数加1，给出3,3,4,2,2,2和2.现在乘以该列表以获得原始号码76576500的约数的个数：3 * 3 * 4 * 2 * 2 * 2 * 2 = 576这里的功能：

def numdiv(n): 
    fs = factors(n) 
    f = fs.pop(0); d = 1; x = 2 
    while fs: 
     if f == fs[0]: 
      x += 1 
     else: 
      d *= x; x = 2 
     f = fs.pop(0) 
    return d * x 

您可以在http://codepad.org/4j8qp60u在工作中看到这些功能，并详细了解他们如何在my blog工作。我会给你解决问题12的解决方案。