1

我正在尽我所能改进这个有趣的算法。

现在,我有这个:

using System;

class Program
{

    static void Main()
    {
        ulong num, largest_pFact;
        uint i = 2;
        string strNum;

        Console.Write("Enter number: ");
        strNum = Console.ReadLine();
        num = ulong.Parse(strNum);
        largest_pFact = num;


        while (i < Math.Sqrt((double) largest_pFact))
        {
            if (i % 2 != 0 | i == 2) {
                if (largest_pFact % i == 0) 
                    largest_pFact /= i;
            }

            i++;
        }

        Console.WriteLine("Largest prime factor of {0} is: {1}", num, largest_pFact);
        Console.ReadLine();

    }
}

那么有什么想法吗?

谢谢!

编辑:我实现了 Ben 的算法,感谢大家的帮助!

4

6 回答 6

2

这里有一个更快的算法。

它消除了平方根并正确处理重复因素。

进一步优化:

static private ulong maxfactor (ulong n)
{
    unchecked
    {
        while (n > 3 && 0 == (n & 1)) n >>= 1;

        uint k = 3;
        ulong k2 = 9;
        ulong delta = 16;
        while (k2 <= n)
        {
            if (n % k == 0)
            {
                n /= k;
            }
            else
            {
                k += 2;
                if (k2 + delta < delta) return n;
                k2 += delta;
                delta += 8;
            }
        }
    }

    return n;
}

这是一个工作演示:http: //ideone.com/SIcIL

于 2011-02-10T00:08:35.597 回答
1

- 将 Math.Sqrt((double) maximum_pFact) 存储在某个变量中,最好是一个 ulong。这避免了每次通过循环都重新计算函数,并且整数比较可能比浮点比较快。您需要将比较更改为 <=。

- 完全避免循环偶数。只需包含 i=2 的特殊情况,然后从 3 处的 i 开始,在每个循环中递增 2。你可以更进一步,让 i=2,3 成为特例,然后只测试 i = 6n+1 或 6n-1。

于 2011-02-10T00:02:37.953 回答
1

好吧,首先我会将特殊情况 2 移出循环,当它可以处理一次时,在整个循环中检查它是没有意义的。如果可能,请使用数据类型int而不是uint,因为它通常更快:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
while (i < Math.Sqrt((double) largest_pFact)) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

平方根计算相对昂贵,因此也应该事先完成:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

然后我会i以两步递增,以消除一个模检查:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

要工作,我相信您需要 awhile而不是if循环内的 a ,否则它将跳过重复的因素:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  while (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}
于 2011-02-10T00:09:50.820 回答
1

一方面,您不需要Math.Sqrt在每次迭代中运行。

    int root = Math.Sqrt((double) largest_pFact);

    while (i < root)
    {
        if ((i % 2 != 0 | i == 2) && largest_pFact % i == 0) {
            largest_pFact /= i;
            root = Math.Sqrt((double) largest_pFact);
        }

        i++;
    }
于 2011-02-10T00:55:39.753 回答
0

我认为:

  • 生成高达num/2的素数
  • 然后从最大到最小检查你num是否可以被素数整除

会更快。

编辑 num/2 NOT sqrt

于 2011-02-10T00:03:05.350 回答
0

在 sqrt(num) 和 2 之间查找总是比从 num/2 开始要快。每个因子对(除了平方根)都有一个小于 sqrt(num) 的数字。

例如:对于 15,int(sqrt(15))==3 15/3=5,因此您通过从 3 而不是 7 开始测试来找到“5”因子。

于 2011-02-10T00:16:17.907 回答