针对计算给定数字的约数数量，最优算法（在性能上）是什么？
如果您能提供伪代码或示例链接，那将非常好。
编辑：所有答案都非常有帮助，谢谢。 我正在实现Atkin筛法，然后将使用类似于Jonathan Leffler指出的方法。 Justin Bozonier发布的链接提供了我所需的更多信息。
计算给定数字的约数数量的算法
183
- sker
4
根据您的要求，得出因子数量是含糊不清的。我猜您想要的是非唯一质因数的数量，因为如果您不需要这个，我可以编写一个程序，始终返回1（如果要分解的数字为1）或2（如果要分解的数字为其他任何数字）。0可能需要更改... - Justin Bozonier
@sker：你需要计算哪个数值范围内的因子？有很多种计算因子的方法，每种方法都更适合特定的范围。 - Ande Turner
2这里有一个相关的有趣问题：http://projecteuler.net/problem=12 - daniloquio
1即使来自编辑后的维基百科文章的天真阿特金筛法在巨大且不切实际的限制下也永远不会比最大化车轮分解的厄拉托色尼筛法更快，并且页面分段版本甚至更加支持SoE（请参见Atkin的合作者Bernstein实施的SoE primesieve与SoA primegen的SoA）常见的不正确的互联网知识是，他们的研究证明了SoA更快，但他们人为地限制了用于证明这一点的SoE的优化。 有关进一步说明，请参见我的SoA答案。 - GordonBGood
26个回答
1
@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;
}
- as2d3
0
我认为这就是你要找的东西。它完全按照你的要求执行。 将其复制并粘贴到记事本中，保存为*.bat文件后运行。输入数字。将该过程乘以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
- dondon
1
882161280 - 1282的因数 - dondon
0
我猜这个会又方便又精确。
script.pyton
>>>因子=[ x for x in range (1,n+1) if n%x==0]
print len(因子)
- Hissaan Ali
0
这不就是一个因数分解的问题吗 - 确定数字的所有因数？然后您可以决定是否需要一个或多个因数的所有组合。
因此，一种可能的算法是：
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
然后就由你来组合这些因素来确定答案的其余部分。
- Jonathan Leffler
0
尝试按照以下方式进行编程：
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;
}
- Bryant James
-1
我不知道最有效的方法，但我会按照以下步骤进行：
- 创建一个素数表，以查找所有小于或等于该数字平方根的素数（个人建议使用Atkin筛法）
- 计算所有小于或等于该数字平方根的素数，并将其乘以二。如果该数字的平方根是整数，则从计数变量中减去一。
应该可以正常工作 \o/
如果需要，我可以明天用C编写一些代码来演示。
- SefBkn
1
3我感到困惑。仅计算小于一个数平方根的所有质数将不会给出它的因子……并非每个小于该数平方根的质数都是该数的因子。 - Garrett Berg
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接