计算给定数字的约数的算法

Question

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

如果您可以提供伪代码或某些示例的链接，那就太好了。

编辑：所有的答案都非常有帮助，谢谢。 我正在实施阿特金筛法，然后我将使用类似于乔纳森·莱夫勒（Jonathan Leffler）指出的东西。 Justin Bozonier 发布的链接提供了有关我想要的更多信息。

Answer 1

我不知道最有效的方法，但我会执行以下操作：

• 创建一个素数表来查找小于或等于数字平方根的所有素数（就我个人而言，我会使用阿特金筛法）
• 计算所有小于或等于该数字的平方根的素数，并将其乘以二。 如果数字的平方根是整数，则从计数变量中减一。

应该可以工作 \o/

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

Answer 2

我想这个会很方便而且精确

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0]
打印 len(因子)

Answer 3

尝试按照以下思路进行操作：

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 4

我想这就是您正在寻找的。我正是按照您的要求做的。
复制并粘贴到记事本中。另存为 *.bat.Run。输入数字。将过程乘以 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

Answer 5

这不就是一个因数分解的问题——确定该数的所有因数吗？ 然后，您可以决定是否需要一个或多个因素的所有组合。

因此，一种可能的算法是：

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 6

这是我写的一个函数。 最坏的时间复杂度是 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 7

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

Answer 8

下面是一个 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++)
{
    ...
}

Answer 9

素数法这里就很清楚了。
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 10

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

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 11

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

现在请注意，对于 pa 素数，τ(p**k) = k+1（p 的幂）。 因此，您可以轻松地通过分解计算 τ(n)。

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

1. 测试数字是否是素数（快速）
2. 如果因此，返回 2
3. 否则，对数字进行因式分解（如果有多个大质因数则速度较慢）
4. 计算 τ (n) 因式分解

Answer 12

除数做了一些惊人的事情：它们完全相除。 如果您想检查数字 n 的除数数量，那么跨越整个范围 1...n 显然是多余的。 我还没有对此进行任何深入的研究，但我解决了 Project Euler 的问题 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;
}

每个算法都有一个弱点。 我认为这对素数来说很弱。 但由于三角形数字不是印刷的，它完美地达到了它的目的。 从我的分析来看，我认为它做得很好。

节日快乐。

Answer 13

您需要阿特金筛，如下所述：http://en.wikipedia.org/wiki/Sieve_of_Atkin< /a>

Answer 14

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

#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

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

不久前有一个素数问题，我做了一个时间测试——对于 32 位整数，至少确定它是否是素数比暴力破解要慢。 有两个因素：

1）虽然人类需要一段时间才能进行除法运算，但他们在计算机上的速度非常快——类似于查找答案的成本。

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

Answer 16

一旦进行了质因数分解，就有一种方法可以找到约数的数量。 每个因子的每个指数加一，然后将指数相乘。

例如：
36
质因数分解：2^2*3^2
除数：1、2、3、4、6、9、12、18、36
除数数：9

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

Answer 17

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

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

Answer 18

阿特金筛法是埃拉托色尼筛法的优化版本，它可以给出给定整数范围内的所有素数。 您应该能够通过谷歌搜索以获取更多详细信息。

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

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

只需一行
我非常仔细地考虑了你的问题，并且尝试编写一段高效且高性能的代码
要在屏幕上打印给定数字的所有除数，我们只需要一行代码！
（通过 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;
}

小就是美:)

Answer 20

这个有趣的问题比看起来要困难得多，而且还没有答案。 这个问题可以分解为两个截然不同的问题。

1 给定 N，找到 N 的质因数的列表 L

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

到目前为止我看到的所有答案都参考#1，但没有提到它对于巨大的数字来说并不容易处理。 对于中等大小的 N，甚至是 64 位数字，这很容易； 对于巨大的 N，因式分解问题可能需要“永远”。 公钥加密取决于此。

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

重申#2，给定包含 k 个项目的集合 C，使得项目 a 有 a' 个重复项，项目 b 有 b' 个重复项，依此类推。有多少种 1 到 k-1 项的唯一组合？ 例如，如果 L = {2,2，则 {2}、{2,2}、{2,2,2}、{2,3}、{2,2,3,3} 必须各自出现一次且仅出现一次,2,3,3,5}。 每个这样的唯一子集合是通过将子集合中的项目相乘得到的N的唯一除数。

Answer 21

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

• 总体概述：http://en.wikipedia.org/wiki/Divisor_function< /p>

• < p>小 n 的值和一些有用的参考：A000005: d(n) （也称为 tau (n) 或 sigma_0(n))，n 的除数数。

• 真实世界示例：整数因式分解

Answer 22

这是一个直接的 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
    if i ** 2 == n:
        count += 1
    return count

Answer 23

我不同意阿特金筛法是可行的方法，因为检查 [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 代码。

Answer 24

@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 25

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

这只是已开发的大量技术之一。 这是一个相当简单的问题。 例如，您需要花很长时间才能学习足够的数论来理解基于椭圆曲线的因式分解技术。 （我知道它们存在。我不理解它们。）

因此，除非您处理小整数，否则我不会尝试自己解决该问题。 相反，我会尝试找到一种方法来使用类似 PARI< /a> 库已经实现了高效的解决方案。 这样我就可以在大约 0.05 秒内分解出一个随机的 40 位数字，例如 124321342332143213122323434312213424231341。 （如果你想知道的话，它的因式分解是 29*439*1321*157907*284749*33843676813*4857795469949。我非常有信心它没有使用阿特金筛来解决这个问题......）

Answer 26

德米特里是对的，你会希望阿特金筛生成素数列表，但我不认为这能解决整个问题。 现在您已经有了一个素数列表，您需要查看其中有多少素数充当除数（以及频率）。

这里有一些用于算法的 python 看这里并搜索“主题：数学 - 需要除数算法”。 只需计算列表中的项目数量，而不是返回它们。

这是数学博士< /a> 这解释了你到底需要用数学方法做什么。

本质上，它可以归结为您的号码 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% 确定我的算法描述，但如果不是的话，那就是类似的东西。