最大的素因子算法优化

我试图尽可能地改进这个有趣的算法。最大的素因子算法优化

现在，我有这样的：

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

    } 
}

所以任何想法？

谢谢！

编辑：我实现了本的算法，谢谢eveyone的帮助！

来源

2011-02-09 Vlad

的[C＃，发现的最大素因子可能重复一个数字]（http://stackoverflow.com/questions/2535251/c-finding-the-largest-prime-factor-of-a-number） – 2011-02-10 00:04:50

你的算法是错误的。什么是16的最大素因子？ – btilly 2011-02-10 00:06:54

是的，你是对的：P – Vlad 2011-02-10 00:20:21

我有一个更快的算法here。

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

进一步优化：

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-10 00:08:35

是的，好主意谢谢本;） – Vlad 2011-02-10 00:16:20

-Store Math.Sqrt（（double）largest_pFact）在某些变量中，最好是ulong。这可以避免每次通过循环都重新计算函数，并且整数比较可能比浮点比较更快。您将需要将比较更改为< =虽然。

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

来源

2011-02-10 00:02:37 Jems

但是，只要找到一个因素，平方根就会改变......当然，平方根根本就不是必需的 – 2011-02-10 00:12:23

在哪一点你更新n umber-额外计算的数量将非常小。虽然我只是试图改进他的算法，而不是果断地增加。 – Jems 2011-02-10 00:19:07

我想：

生成素数高达num/2
然后从大检查，以最低的，如果你的num是整除的首要

会更快。

编辑NUM/2不开方

来源

2011-02-10 00:03:05 damienix

这可能适用于较小的数字，但对于大数字将花费太多。 – Vlad 2011-02-10 00:08:00

嗯，首先我会的特殊情况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 2步，以elliminate一个模校验：

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

工作，我相信你需要while代替环内的if，否则将跳过被重复的因素：

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-10 00:09:50 Guffa

它总是更快的sqrt（NUM）和2之间看起来比它在NUM/2开始。每个因素对（除了平方根之外）都有一个小于sqrt（num）的数字。

例：对于15，INT（SQRT（15））== 3 15/3 = 5，所以你通过启动你的测试在3发现代替7.

来源

2011-02-10 00:16:17 khedoros

“5” 因子对于一个事情，你不需要在每次迭代中运行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-10 00:55:39

-1

这是我的尝试，但我不知道这是否是正确的... Dosent与庞大的数字工作：（（

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace PrimeFactor 
{ 
class Program 
{ 
    static void Main(string[] args) 
    { 

     Int64 i, y =65; 
     List<Int64> PrimeFactor = new List<Int64>(); 
     for (i = 2; i <65; i++) 
     { 
      if (y % i == 0) 
      { 
       y = y/i; 
       PrimeFactor.Add(i); 



       } 
      } 
     PrimeFactor.Sort(); 

     foreach (Int64 j in PrimeFactor) 
     { 
      Console.WriteLine(j); 
     } 

     } 


     } 
     }

来源

2014-02-02 02:08:46 user3137638

最大的素因子算法优化

回答

相关问题