algorithm给定数的除数

计算给定数字的除数的最佳algorithm（性能方面）是什么？

如果你能提供伪代码或者某个例子的链接，那将是非常好的。

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

Answer 1

德米特里是正确的，你会希望阿特金的筛子产生主要名单，但我不相信，照顾整个问题。 现在你有一个素数列表，你需要看看有多less个素数作为除数（以及多less次）。

这里是algorithm的一些python在 这里find并search“主题：math – 需要除数algorithm”。 只需计算列表中的项目数量，而不是返回它们。

这里有一个博士math ，解释什么是你需要做的math。

基本上归结为如果你的数字是：
n = a^x * b^y * c^z
（其中a，b和c是n的主除数，x，y和z是除数重复的次数），那么所有除数的总计数为：
(x + 1) * (y + 1) * (z + 1) 。

编辑：顺便说一句，要find一个，B，C等，你会想做什么相当于一个贪婪的algorithm，如果我正确理解这一点。 从你的最大素数除数开始，并乘以它自己，直到进一步的乘法将超过数字n。 然后移动到下一个最低因子，乘以当前素数乘以前一个素数^倍，并保持乘以素数，直到下一个将超过n …等等。跟踪乘以并将这些数字应用到上面的公式中。

不是100％确定我的algorithm描述，但如果不是这样，它是类似的东西。

Answer 2

除了Atkin的筛，还有更多的分解技术。 例如，假设我们想要因子5893.那么它的sqrt是76.76 …现在我们将尝试把5893写成正方形的乘积。 （77 * 77 – 5893）= 36，它是6平方，所以5893 = 77 * 77 – 6 * 6 =（77 + 6）（77-6）= 83 * 71。 如果没有奏效的话，我们会看看78 * 78 – 5893是不是一个完美的方形。 等等。 使用这种技术，您可以快速testingn个平方根附近的因子，比通过testing单个素数快得多。 如果将这种技术与筛子一起排除大的素数，那么比单独使用筛子将会有更好的因子分解方法。

而这只是大量已经开发的技术之一。 这是一个相当简单的。 要学习足够的数论来理解基于椭圆曲线的保理技术需要很长时间。 （我知道他们存在，我不明白他们）

因此，除非你处理小整数，否则我不会自己去解决这个问题。 相反，我会尝试find一种方法来使用像PARI库，已经有一个高效率的解决scheme实施。 有了这个，我可以在大约.05秒内随机分配一个40位的数字，比如124321342332143213122323434312213424231341。 （它的因式分解，如果你想知道的话，是29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949。我相当确信它没有通过Atkin的筛选来解决这个问题…）

Answer 3

@Yasky

你的除数函数有一个错误，因为它不能正确工作的完美正方形。

尝试：

 int divisors(int x) { int limit = x; int numberOfDivisors = 0; if (x == 1) return 1; for (int i = 1; i < limit; ++i) { if (x % i == 0) { limit = x / i; if (limit != i) { numberOfDivisors++; } numberOfDivisors++; } } return numberOfDivisors; } 

Answer 4

我不同意阿特金的筛选方法是要走的，因为检查[1，n]中每一个数字的素数都可能要花费更长的时间，而不是按照分裂来减less数量。

下面是一些代码，虽然稍微有些黑，但通常要快得多：

 import operator # A slightly efficient superset of primes. def PrimesPlus(): yield 2 yield 3 i = 5 while True: yield i if i % 6 == 1: i += 2 i += 2 # Returns a dict d with n = product p ^ d[p] def GetPrimeDecomp(n): d = {} primes = PrimesPlus() for p in primes: while n % p == 0: n /= p d[p] = d.setdefault(p, 0) + 1 if n == 1: return d def NumberOfDivisors(n): d = GetPrimeDecomp(n) powers_plus = map(lambda x: x+1, d.values()) return reduce(operator.mul, powers_plus, 1) 

PS这是工作python代码来解决这个问题。

Answer 5

这个有趣的问题比看起来更难，而且还没有得到回答。 这个问题可以分解成两个非常不同的问题。

1给定N，findN的主要因素列表L.

2给定L，计算唯一组合的数量

我看到的所有答案到目前为止都是＃1，并没有提及它是不容易处理的庞大的数字。 对于中等大小的N，甚至是64位数字，很容易; 对于巨大的N来说，保理问题可以采取“永久的”。 公钥encryption取决于此。

问题＃2需要更多的讨论。 如果L仅包含唯一的数字，则使用组合公式从n个项目中selectk个对象进行简单的计算。 实际上，需要将k从1变化到sizeof（L）时，应用公式的结果。 但是，L通常会包含多次出现的多个素数。 例如，L = {2,2,2,3,3,5}是N = 360的因式分解。现在这个问题相当困难！

重述＃2，给定包含k个项目的集合C，使得项目a具有'重复项目，并且项目b具有b'重复项目，等等.1到k-1项目的唯一组合是多less？ 例如，如果L = {2,2}，{2,2}，{2,2,2}，{2,3}，{2,2,3,3} ，2,3,3,5}。 每个这样的独特的子集合是N的唯一因子乘以子集合中的项目。

Answer 6

你的问题的答案很大程度上取决于整数的大小。 对于小数字（例如小于100位）和数字〜1000位（例如在密码学中使用）的方法是完全不同的。

• 一般概述： http : //en.wikipedia.org/wiki/Divisor_function

• （n）（也称为tau（n）或sigma_0（n））是n的除数。

• 真实世界的例子： 整数分解

Answer 7

这是一个简单的O（sqrt（n））algorithm。 我用这个来解决项目euler

 def divisors(n): count=2 # accounts for 'n' and '1' i=2 while(i**2 < n): if(n%i==0): count+=2 i+=1 count+=(1 if i**2==n else 0) return count 

Answer 8

只有一行
我非常小心地考虑了你的问题，并试图编写一个高效率，高性能的代码。要在屏幕上打印给定数字的所有除数，我们只需要一行代码！ （在通过gcc编译时使用选项-std = c99）

 for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number 

为find除数的数量，您可以使用以下非常非常快速的function（除1和2以外的所有整数）

 int number_of_divisors(int n) { int counter,i; for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++); return counter; } 

或者如果您将给定的数字作为除数（对于除1和2之外的所有整数都正确工作）

 int number_of_divisors(int n) { int counter,i; for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++); return ++counter; } 

注意：以上两个函数对于除1和2之外的所有正整数都是正确的，因此对于大于2的所有数字都是可用的，但是如果您需要覆盖1和2，则可以使用以下函数之一比较慢）

 int number_of_divisors(int n) { int counter,i; for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++); if (n==2 || n==1) { return counter; } return ++counter; } 

要么

 int number_of_divisors(int n) { int counter,i; for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++); return ++counter; } 

小是美丽:)

我还在波斯语的http://cnevis.com/?p=196下面的链接中解释了上述代码;

Answer 9

阿特金的滤网是Eratosthenes滤网的优化版本，它可以给所有素数达到给定的整数。 你应该可以谷歌这个更多的细节。

一旦你有了这个列表，把每个素数除以你的数字是一个简单的事情，看看它是一个确切的除数（即余数为零）。

计算数字（n）的除数的基本步骤是[这是伪代码从实际代码转换，所以我希望我没有引入错误]：

 for z in 1..n: prime[z] = false prime[2] = true; prime[3] = true; for x in 1..sqrt(n): xx = x * x for y in 1..sqrt(n): yy = y * y z = 4*xx+yy if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)): prime[z] = not prime[z] z = z-xx if (z <= n) and (z mod 12 == 7): prime[z] = not prime[z] z = z-yy-yy if (z <= n) and (x > y) and (z mod 12 == 11): prime[z] = not prime[z] for z in 5..sqrt(n): if prime[z]: zz = z*z x = zz while x <= limit: prime[x] = false x = x + zz for z in 2,3,5..n: if prime[z]: if n modulo z == 0 then print z 

Answer 10

一旦你有主因式分解，有一种方法来find除数的数量。 将每个指数中的每个因子加1，然后将指数相乘。

例如：36素分解：2 ^ 2 * 3 ^ 2因数：1,2,3,4,6,9,12,18,36因数的个数：9

给每个指数加一个2 ^ 3 * 3 ^ 3乘法指数：3 * 3 = 9

Answer 11

你可以试试这个。 这有点冒险，但速度相当快。

 def factors(n): for x in xrange(2,n): if n%x == 0: return (x,) + factors(n/x) return (n,1) 

Answer 12

在您提交解决scheme之前，请考虑Sieve方法在典型情况下可能不是一个好答案。

一段时间后，有一个主要问题，我做了一个时间testing – 对于32位整数，至less确定是否是素数比蛮力慢。 有两个因素在进行：

1）虽然一个人需要一段时间来进行分工，但他们在计算机上的速度非常快 – 类似于查找答案的成本。

2）如果你没有主表，你可以做一个完全在L1caching中运行的循环。 这使得它更快。

Answer 13

因子做了一些壮观的事情：他们完全分裂。 如果你想检查一个数n的除数，显然是跨越整个频谱1...n冗余。 我没有为此做过任何深入的研究，但是我解决了欧拉在三angular数据上的问题12 。 我的解决scheme500以上的除数testing运行了309504微秒（〜0.3s）。 我为解决scheme写了这个除数函数。

 int divisors (int x) { int limit = x; int numberOfDivisors = 1; for (int i(0); i < limit; ++i) { if (x % i == 0) { limit = x / i; numberOfDivisors++; } } return numberOfDivisors * 2; } 

对于每个algorithm，都有一个弱点。 我认为这对于素数很弱。 但是由于三angular形数字不是印刷的，所以它完美地达到了它的目的。 从我的描述来看，我认为它做得很好。

节日快乐。

Answer 14

这是一个有效的解决scheme：

 #include <iostream> int main() { int num = 20; int numberOfDivisors = 1; for (int i = 2; i <= num; i++) { int exponent = 0; while (num % i == 0) { exponent++; num /= i; } numberOfDivisors *= (exponent+1); } std::cout << numberOfDivisors << std::endl; return 0; } 

Answer 15

你想要的是Atkin的筛，这里描述： http : //en.wikipedia.org/wiki/Sieve_of_Atkin

Answer 16

质数方法在这里非常明确。 P []是小于或等于sq = sqrt（n）的素数列表;

 for (int i = 0 ; i < size && P[i]<=sq ; i++){ nd = 1; while(n%P[i]==0){ n/=P[i]; nd++; } count*=nd; if (n==1)break; } if (n!=1)count*=2;//the confusing line :D :P . i will lift the understanding for the reader . i now look forward to a method more optimized . 

Answer 17

数论教科书称之为除数计数函数τ。 第一个有趣的事实是，它是乘法的，即。 τ（ab）=τ（a）τ（b），当a和b没有公因子时。 （certificate：a和b的每一对除数都给出了ab的一个不同的除数）。

现在注意，对于素数，τ（p ** k）= k + 1（p的幂）。 因此，您可以轻松地从其因式分解中计算τ（n）。

然而，大数分解可能是缓慢的（RSA冷冻的安全性取决于两个大质数的产物难以分解）。 这表明这个优化的algorithm

1. testing数字是否为素数（快速）
2. 如果是，则返回2
3. 否则， 将数字因子分解 （如果有多个大素数因子，则慢）
4. 从因式分解中计算τ（n）

Answer 18

以下是一个C程序来查找给定数字的除数。

上述algorithm的复杂度是O（sqrt（n））。

这个algorithm对于完美平方的数字以及不是完美平方的数字都是正确的。

请注意，循环的上限设置为数字的平方根以使algorithm最有效。

请注意，将上限存储在单独的variables中也可节省时间，因此不应在for循环的条件部分中调用sqrt函数，这也会节省您的计算时间。

 #include<stdio.h> #include<math.h> int main() { int i,n,limit,numberOfDivisors=1; printf("Enter the number : "); scanf("%d",&n); limit=(int)sqrt((double)n); for(i=2;i<=limit;i++) if(n%i==0) { if(i!=n/i) numberOfDivisors+=2; else numberOfDivisors++; } printf("%d\n",numberOfDivisors); return 0; } 

而不是上面的for循环，你也可以使用下面的循环更有效，因为这不需要find数字的平方根。

 for(i=2;i*i<=n;i++) { ... } 

Answer 19

这是我写的一个函数。 最差的时间复杂度是O（sqrt（n）），另一方面最好的时间是O（log（n））。 它给你所有的主要因数，以及它的发生次数。

 public static List<Integer> divisors(n) { ArrayList<Integer> aList = new ArrayList(); int top_count = (int) Math.round(Math.sqrt(n)); int new_n = n; for (int i = 2; i <= top_count; i++) { if (new_n == (new_n / i) * i) { aList.add(i); new_n = new_n / i; top_count = (int) Math.round(Math.sqrt(new_n)); i = 1; } } aList.add(new_n); return aList; } 

Answer 20

这是计算分子数的最基本的方法：

 class PrintDivisors { public static void main(String args[]) { System.out.println("Enter the number"); // Create Scanner object for taking input Scanner s=new Scanner(System.in); // Read an int int n=s.nextInt(); // Loop from 1 to 'n' for(int i=1;i<=n;i++) { // If remainder is 0 when 'n' is divided by 'i', if(n%i==0) { System.out.print(i+", "); } } // Print [not necessary] System.out.print("are divisors of "+n); } } 

Answer 21

@Kendall

我testing了你的代码并做了一些改进，现在更快了。 我还testing了@هومنجاویدپور代码，这也比他的代码更快。

 long long int FindDivisors(long long int n) { long long int count = 0; long long int i, m = (long long int)sqrt(n); for(i = 1;i <= m;i++) { if(n % i == 0) count += 2; } if(n / m == m && n % m == 0) count--; return count; } 

Answer 22

这不仅仅是把数字因素考虑在内的问题 – 决定数字的所有因素？ 您可以决定是否需要一个或多个因素的所有组合。

所以，一个可能的algorithm是：

 factor(N) divisor = first_prime list_of_factors = { 1 } while (N > 1) while (N % divisor == 0) add divisor to list_of_factors N /= divisor divisor = next_prime return list_of_factors 

然后由您来决定剩下的答案。

Answer 23

这是我根据贾斯丁的回答想出来的。 这可能需要一些优化。

 n=int(input()) a=[] b=[] def sieve(n): np = n + 1 s = list(range(np)) s[1] = 0 sqrtn = int(n**0.5) for i in range(2, sqrtn + 1): if s[i]: s[i*i: np: i] = [0] * len(range(i*i, np, i)) return filter(None, s) k=list(sieve(n)) for i in range(len(k)): if n%k[i]==0: a.append(k[i]) a.sort() for i in range(len(a)): j=1 while n%(a[i]**j)==0: j=j+1 b.append(j-1) nod=1 for i in range(len(b)): nod=nod*(b[i]+1) print('no.of divisors of {} = {}'.format(n,nod)) 

Answer 24

我想这就是你要找的东西。我正是你所要求的。 复制并粘贴到记事本中。保存为* .bat.Run.Enter Number.Multiply进程的2，这就是除数的数量。我故意这样确定除数更快：

请注意，一个CMD varriable支持超过999999999的值

 @echo off modecon:cols=100 lines=100 :start title Enter the Number to Determine cls echo Determine a number as a product of 2 numbers echo. echo Ex1 : C = A * B echo Ex2 : 8 = 4 * 2 echo. echo Max Number length is 9 echo. echo If there is only 1 proces done it echo means the number is a prime number echo. echo Prime numbers take time to determine echo Number not prime are determined fast echo. set /p number=Enter Number : if %number% GTR 999999999 goto start echo. set proces=0 set mindet=0 set procent=0 set B=%Number% :Determining set /a mindet=%mindet%+1 if %mindet% GTR %B% goto Results set /a solution=%number% %%% %mindet% if %solution% NEQ 0 goto Determining if %solution% EQU 0 set /a proces=%proces%+1 set /a B=%number% / %mindet% set /a procent=%mindet%*100/%B% if %procent% EQU 100 set procent=%procent:~0,3% if %procent% LSS 100 set procent=%procent:~0,2% if %procent% LSS 10 set procent=%procent:~0,1% title Progress : %procent% %%% if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number% goto Determining :Results title %proces% Results Found echo. @pause goto start 

Answer 25

我想这一个将是方便和精确的

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Answer 26

尝试一下这些方面：

 int divisors(int myNum) { int limit = myNum; int divisorCount = 0; if (x == 1) return 1; for (int i = 1; i < limit; ++i) { if (myNum % i == 0) { limit = myNum / i; if (limit != i) divisorCount++; divisorCount++; } } return divisorCount; } 

Answer 27

我不知道最有效的方法，但我会做以下几点：

• 创build一个素数表来查找小于或等于数字平方根的所有素数（就个人而言，我会使用Atkin的筛子）
• 计算小于或等于数的平方根的所有素数，并乘以2。 如果数字的平方根是整数，则从countvariables中减去一个。

应该工作\ o /

如果你需要的话，我可以在C代码明天用C来演示。