计算给定数量的除数的最佳算法（性能方面）是什么？
如果您能提供伪代码或链接到一些示例，那将会很棒。
编辑：所有答案都非常有帮助，谢谢。我正在实施Atkin的Sieve，然后我将使用类似于Jonathan Leffler所指出的东西。 Justin Bozonier发布的链接提供了我想要的更多信息。
德米特里是对的，你会希望阿特金的筛子产生最佳清单，但我不认为这会解决整个问题。既然你有一个素数列表，你需要看看有多少素数作为除数（以及多久）。
Here's some python for the algo Look here并搜索“主题：数学 - 需要除数算法”。只计算列表中的项目数，而不是返回它们。
Here's a Dr. Math解释了你需要用数学方法做什么。
基本上它归结为如果您的数字n是：
n = a^x * b^y * c^z
（其中a，b和c是n的素数除数，x，y和z是除数重复的次数）则所有除数的总数是：
(x + 1) * (y + 1) * (z + 1)。
编辑：顺便说一句，如果我正确理解这一点，你会想要做一个贪婪的算法，你会发现a，b，c等。从最大的素数除数开始，将其自身相乘，直到进一步的乘数超过数n。然后移动到下一个最低因子并乘以前一个素数^它乘以当前素数的次数并保持乘以素数直到下一个将超过n ...等等。跟踪你乘以的次数除数一起并将这些数字应用到上面的公式中。
不是100％肯定我的算法描述，但如果不是它，它是类似的东西。
你可以试试这个。它有点hackish，但速度相当快。
def factors(n):
for x in xrange(2,n):
if n%x == 0:
return (x,) + factors(n/x)
return (n,1)
一旦你进行了素数分解，就有办法找到除数的数量。在每个单独的因子上为每个指数添加一个，然后将指数相乘。
例如：36素因子分解：2 ^ 2 * 3 ^ 2除数：1,2,3,4,6,9,12,18,36除数数：9
为每个指数加1 ^ 3 * 3 ^ 3乘以指数：3 * 3 = 9
在您提交解决方案之前，请考虑在典型情况下，Sieve方法可能不是一个好的答案。
前一段时间有一个主要问题，我做了一个时间测试 - 对于32位整数，至少确定它是否是素数比蛮力慢。有两个因素：
1）虽然人类需要一段时间才能进行划分，但他们在计算机上的速度非常快 - 类似于查找答案的成本。
2）如果你没有素数表，你可以创建一个完全在L1缓存中运行的循环。这使它更快。
这是一个有效的解决方案：
#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;
}
除数做得很壮观：它们完全分开。如果你想检查一个数字的除数的数量，n，它显然是多余的跨越整个频谱，1...n。我没有对此进行任何深入的研究，但我解决了Project Euler's problem 12 on Triangular Numbers。我对大于500的除数测试的解决方案运行了309504微秒（~0.3s）。我为解决方案编写了这个除数函数。
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;
}
对于每种算法，都存在一个弱点。我认为这对素数很弱。但由于三角形数字不是印刷品，因此它完美地实现了它的目的。从我的分析，我认为它做得很好。
节日快乐。
你想要这里描述的阿特金筛子：http://en.wikipedia.org/wiki/Sieve_of_Atkin
素数方法在这里很清楚。 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 .
数论教科书称为除数计数函数tau。第一个有趣的事实是，它是乘法的，即。 τ（ab）=τ（a）τ（b），当a和b没有公因子时。 （证明：a和b的每对除数都给出了ab的明显除数）。
现在注意，对于p素数，τ（p ** k）= k + 1（p的幂）。因此，您可以从其因子分解中轻松计算τ（n）。
然而，分解大数字可能会很慢（RSA crytopraphy的安全性取决于两个大质量的产品难以分解）。这表明这种优化算法
以下是一个C程序，用于查找给定数字的除数。
上述算法的复杂度为O（sqrt（n））。
该算法可以正确地处理完美正方形的数字以及不完美正方形的数字。
请注意，循环的上限设置为数字的平方根，以使算法最有效。
请注意，将上限存储在单独的变量中也可以节省时间，不应该在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循环，您还可以使用以下循环，这样更有效，因为这样就无需找到数字的平方根。
for(i=2;i*i<=n;i++)
{
...
}
这是我写的一个函数。它的最差时间复杂度是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;
}
除了阿特金的筛子，还有很多分解技术。例如，假设我们想要因子5893.那么它的sqrt是76.76 ......现在我们将尝试将5893写为正方形的乘积。那么（77 * 77-8593）= 36这是6平方，所以5893 = 77 * 77-6 * 6 =（77 + 6）（77-6）= 83 * 71。如果那还行不通，我们会看看78 * 78 - 5893是否是一个完美的广场。等等。使用这种技术，您可以快速测试n的平方根附近的因子，比测试单个素数要快得多。如果将这种技术与筛子一起排除大质数，你就会有比单独使用筛子更好的保理方法。
这只是已经开发的大量技术之一。这是一个相当简单的问题。你需要花费很长时间来学习足够的数论来理解基于椭圆曲线的分解技术。 （我知道它们存在。我不明白它们。）
因此，除非你处理小整数，否则我不会尝试自己解决这个问题。相反，我试图找到一种方法来使用已经实现了高效解决方案的PARI库。有了它，我可以在大约.05秒内计算一个随机的40位数字，如124321342332143213122323434312213424231341。 （如果你想知道的话，它的分解是29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949。我非常有信心，它没有用阿特金的筛子来解决这个问题......）
这是计算数字分割的最基本方法：
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);
}
}
@Kendall
我测试了你的代码并做了一些改进，现在它更快了。我还测试了@هومنجاویدپور代码，这也比他的代码更快。
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;
}
这不仅仅是一个考虑数字的问题 - 确定数字的所有因素？然后，您可以决定是否需要一个或多个因素的所有组合。
因此，一种可能的算法是：
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
然后由您来组合这些因素以确定答案的其余部分。
这是我根据贾斯汀的回答提出的。可能需要一些优化。
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))
我认为这就是你要找的东西。我的确完全符合你的要求。复制并粘贴在Notepad.Save中* .bat.Run.Enter Number.Multiply the process by 2，这就是除数的数量。我故意这样做，所以它更快地确定了除数：
请注意，CMD变量可以支持超过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
我想这个会很方便，也很准确
>>>factors=[ x for x in range (1,n+1) if n%x==0]
print len(factors)
尝试这些方面的东西：
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;
}
您可以将素数预先计算到最大可能N的sqaure根，并计算数字的每个素数因子的指数。 n的除数（n = p1 ^ a p2 ^ b p3 ^ c ...）是（a + 1）（b + 1）（c + 1），因为它与计算组合素数的方式相同这些因素的数量（这将计算除数的数量）。如果预先计算素数，这非常快
有关此方法的更多详细信息：
https://mathschallenge.net/library/number/number_of_divisors
https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html
http://primes.utm.edu/glossary/xpage/tau.html
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int divisors_count(const vector<int>& primes, int n)
{
int divisors = 1;
for (int i = 0; i < primes.size(); ++i) {
int factor = primes[i];
int factor_exponent = 0;
while (n % factor == 0) {
++factor_exponent;
n /= factor;
}
divisors *= (factor_exponent + 1);
}
if (n > 1)
return 2*divisors; // prime factor > sqrt(MAX_N)
return divisors;
}
int main()
{
const int MAX_N = 1e6;
int max_factor = sqrt(MAX_N);
vector<char> prime(max_factor + 1, true);
for (int i = 3; i <= max_factor; i += 2) {
if (prime[i]) {
for (int j = 3*i; j <= max_factor; j += 2*i) {
prime[j] = false;
}
}
}
vector<int> primes;
primes.reserve(max_factor/2);
primes.push_back(2);
for (int i = 3; i <= max_factor; i += 2) {
if (prime[i]) {
primes.push_back(i);
}
}
int n;
while (cin >> n) {
cout << divisors_count(primes, n) << endl;
}
}
我不知道最有效的方法，但我会做以下事情：
应该工作\ o /
如果您需要，我可以在C中明天编写代码以进行演示。
@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;
}
我不同意阿特金的筛子是要走的路，因为它可能很容易花费更长的时间来检查[1，n]中的每个数字的原始性，而不是通过分割来减少数量。
这里有一些代码虽然稍微有点粗俗，但通常要快得多：
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代码。
这个有趣的问题比它看起来要难得多，而且还没有得到回答。这个问题可以归结为两个截然不同的问题。
到目前为止，我看到的所有答案都提到了＃1，并且没有提到它对于大量数字而言并不易处理。对于中等大小的N，甚至是64位数字，它很容易;对于巨大的N，因子分解问题可以“永远”。公钥加密取决于此。
问题＃2需要更多讨论。如果L仅包含唯一数字，则使用组合公式从n个项目中选择k个对象是一个简单的计算。实际上，您需要将应用公式的结果相加，同时将k从1变为sizeof（L）。但是，L通常会包含多次出现的多个素数。例如，L = {2,2,2,3,3,5}是N = 360的因式分解。现在这个问题非常困难！
重申＃2，给定集合C包含k个项目，使得项目a具有'重复项，项b具有b'重复项等，有多少1到k-1个项目的独特组合？例如，{2}，{2,2}，{2,2,2}，{2,3}，{2,2,3,3}必须每次出现一次，如果L = {2,2，则只出现一次，2,3,3,5}。通过乘以子集合中的项目，每个这样的唯一子集合是N的唯一除数。
您的问题的答案在很大程度上取决于整数的大小。小数的方法，例如少于100位，对于数字~1000位（如用于密码学）则完全不同。
这是一个直接的O（sqrt（n））算法。我用它来解决project 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
只需一行 我非常关心你的问题，我试着编写一个高效且高性能的代码片段要在屏幕上打印给定数字的所有除数，我们只需要一行代码！ （通过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
要查找除数的数量，您可以使用以下非常快的函数（对除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;
}
小很漂亮:)
Atkin的筛子是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