你想要阿特金的筛子，这里描述: http://en.wikipedia.org/wiki/Sieve_of_Atkin

这难道不仅仅是一个数字因子的问题吗? 它决定了数字的所有因子？然后您可以决定是否需要一个或多个因素的所有组合。

所以，一种可能的算法是:

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

然后由你来综合这些因素来决定剩下的答案。

德米特里说得对，你会希望阿特金的筛子生成基本列表，但我不认为这样就能解决整个问题。现在您已经有了一个素数列表，接下来您需要了解其中有多少个素数作为除数(以及作为除数的频率)。

下面是一些用于算法 看这里的 Python，并搜索“ Subject: 數学-需要除数算法”。只需计算列表中的项数，而不是返回它们。

这里有一个数学博士解释了什么是你确切需要做的数学。

我不知道最有效的方法，但我会这样做:

• 创建一个素数表，找出所有小于或等于数字平方根的素数(个人而言，我会使用阿特金筛)
• 计算所有小于或等于该数字平方根的素数，并将其乘以2。如果数字的平方根是一个整数，那么从 count 变量中减去1。

应该可以

如果需要的话，我明天可以用 C 语言编写一些代码来演示。

阿特金的筛子是一个优化版本的埃拉托斯特尼筛法，它给所有的素数到一个给定的整数。你应该可以谷歌更多的细节。

一旦你有了这个列表，用每个素数除以你的数字，看看它是否是一个精确的除数(也就是说，余数为零)就很简单了。

计算数字(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

有一个 很多更多的技术保理比阿特金的筛子。例如，假设我们想要因子5893。它的 sqrt 是76.76... 现在我们试着写出5893作为正方形的乘积。Well (77 * 77-5893) = 36，等于6的平方，所以5893 = 77 * 77-6 * 6 = (77 + 6)(77-6) = 83 * 71。如果那不起作用，我们就会看看78 * 78-5893是否是一个完美的正方形。诸如此类。使用这种技术，您可以快速测试接近 n 的平方根的因子，比测试单个素数要快得多。如果您将这种技术与筛子结合起来排除大素数，那么您将拥有比单独使用筛子更好的分解方法。

这只是众多技术中的一项。这是一个相当简单的问题。比如说，学习足够的数论来理解基于椭圆曲线的因式分解技术需要花费很长的时间。(我知道它们存在。我不理解他们。)

因此，除非你处理的是小整数，否则我不会尝试自己解决这个问题。相反，我会尝试找到一种方法来使用类似于 巴黎库的东西，它已经实现了一个高效的解决方案。通过这个方法，我可以在0.05秒内计算出一个随机的40位数，比如12432134233431223434312213424231341。(如果你想知道，它的因子分解是29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949。我非常确信它不是通过阿特金的筛子来解决这个问题的... ...)

你问题的答案很大程度上取决于整数的大小。对于小数字(例如小于100位)和对于大于1000位(例如用于加密)的方法是完全不同的。

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

• 值的小 n和一些有用的参考: A000005: d (n)(也称为 tau (n)或 sigma _ 0(n)) ，n 的除数个数。

• 现实世界的例子: 整数的因数分解

我不同意阿特金筛选法的做法，因为检查[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，求 N 的素因子列表 L

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

到目前为止，我所看到的所有答案都提到了第一点，但没有提到，对于庞大的数字来说，这个问题是难以处理的。对于中等大小的 N，甚至是64位数字，这很容易; 对于巨大的 N，因子分解问题可能需要“很长时间”。公钥加密依赖于此。

第二个问题需要进一步讨论。如果 L 只包含唯一的数字，这是一个简单的计算，使用组合公式从 n 个项目中选择 k 对象。实际上，当 k 从1变化到 sizeof (L)时，需要求出应用公式的结果之和。但是，L 通常包含多个素数的多次出现。例如，L = {2,2,2,3,3,5}是 N = 360的因子分解。现在这个问题相当难了！

重述 # 2，给定包含 k 个项目的集合 C，比如项目 a 有一个’重复项目，项目 b 有 b’重复项目，等等，有多少个1到 k-1个项目的唯一组合？例如，如果 L = {2,2,2} ，{2,2,2} ，{2,2,2} ，{2,2,3,3}必须各出现一次且只出现一次。通过将子集合中的项相乘，每个这样的唯一子集合都是 N 的唯一除数。

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

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

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

不久之前，有一个质数问题，我做了一个时间测试——对于32位整数来说，至少判断质数是否比蛮力慢。有两个因素在起作用:

1)人类做除法需要一段时间，但他们在计算机上的速度非常快——类似于查找答案的成本。

2)如果没有素数表，可以创建一个完全在 L1缓存中运行的循环。这样更快。

一旦你有了整数分解，就有办法找出除数的个数。在每个因子的每个指数上加一个，然后将这些指数相乘。

例如: 36 整数分解: 22 * 32 除数: 1,2,3,4,6,9,12,18,36 除数: 9

向每个指数2 ^ 3 * 3 ^ 3加一 乘法指数: 3 * 3 = 9

除数做了一些惊人的事情: 它们完全除法。如果你想检查一个数字的除数数目，n，它显然是多余的，以跨越整个频谱，1...n。我没有做任何深入的研究，但我解决了 关于三角数的欧拉问题12。我的 大于500除数测试解决方案运行了309504微秒(约0.3秒)。我写了这个解决方案的除数函数。

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;
}

每个算法都有弱点。我以为这个对付质数很弱。但是因为三角数字不是打印出来的，所以它完美地达到了目的。从侧写来看，我觉得还不错。

节日快乐。

@ 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;
}

就一句
我已经非常仔细地考虑了您的问题，并且尝试编写一段高效和高性能的代码 要在屏幕上打印给定数字的所有除数，我们只需要一行代码！ (通过 gcc 进行编译时使用 option-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;
}

小就是美:)

素数方法在这里非常清楚。 P []是小于或等于平方 = 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  .

下面是一个直接的 O (sqrt (n))算法

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

数论教科书称之为除数计数函数 tau。第一个有趣的事实是它是乘法的。Τ (ab) = τ (a) τ (b) ，当 a 和 b 没有公因数时。(证明: a 和 b 的每对约数都给出了 ab 的一个不同的约数)。

现在注意对于 p a 素数 τ (p * * k) = k + 1(p 的幂)。因此，你可以很容易地从它的因式分解计算 τ (n)。

然而，对大数进行因子分解可能会很慢(RSA 密码的安全性取决于两个大素数的乘积难以进行因子分解)。这表明这个优化算法

1. 测试数字是否为质数(快速)
2. 如果是，返回2
3. 否则，将数字因数分解(如果有多个较大的素因子，则速度较慢)
4. 从因式分解计算 τ (n)

下面是一个 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;
}

这是一个有效的解决方案:

#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;
}

这是计算数除数的最基本方法:

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);


}
}

我想这就是你要找的，我完全按你说的做了。 复制并粘贴到记事本中。保存为 * 。蝙蝠。快跑。输入号码。把这个过程乘以2就是除数的个数我故意这么做的这样它就能更快地确定除数:

请注意，CMD 变量不能支持超过99999999的值

@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

@ 肯德尔

我测试了你的代码并做了一些改进，现在它更快了。 我还测试了@code，这也比他的代码快。

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;
}

我想这个既方便又精确

Script.pyton

如果 n% x = = 0，则在(1，n + 1)的范围内，> > 因子 = [ x x ] 打印镜头(因子)

试试下面这些方法:

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;
}