C＃，找到一个数字的最大素数因子

我是编程新手，我正在练习C＃编程技巧。 我的应用程序旨在找到用户输入的数字的最大素数因子。 但我的应用程序没有返回正确的答案，我真的不知道问题在哪里。 你能帮我么？

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { Console.WriteLine("Calcular máximo factor primo de n. De 60 es 5."); Console.Write("Escriba un numero: "); long num = Convert.ToInt64(Console.ReadLine()); long mfp = maxfactor(num); Console.WriteLine("El maximo factor primo es: " + num); Console.Read(); } static private long maxfactor (long n) { long m=1 ; bool en= false; for (long k = n / 2; !en && k > 1; k--) { if (n % k == 0 && primo(k)) { m = k; en = true; } } return m; } static private bool primo(long x) { bool sp = true; for (long i = 2; i <= x / 2; i++) { if (x % i == 0) sp = false; } return sp; } } } 

Answer 1

在残留物为素数之前，除去小因子会快得多。

 static private long maxfactor (long n) { long k = 2; while (k * k <= n) { if (n % k == 0) { n /= k; } else { ++k; } } return n; } 

例如，如果n = 784，则执行9次模运算而不是数百次运算。 即使使用sqrt限制，倒计时仍会在maxfactor中执行21个模运算，在primo中执行另外12个模运算。

这里有更新的优化版本

Answer 2

 Console.WriteLine("El maximo factor primo es: " + mfp); 

代替

 Console.WriteLine("El maximo factor primo es: " + num); 

Answer 3

你有条件（！en）使它只迭代直到第一个素数因子。 您也可以将界限从n / 2减少到sqrt（n）+1

Answer 4

Catalin DICU已经回答了你的问题，但你的代码中有一些非惯用的构造，你应该看看重构。 例如，在你的maxfactor方法中，你不需要“en”条件，只要你找到它就立即返回值：

 static private long maxfactor (long n) { for (long k = n / 2; k > 1; k--) { if (n % k == 0 && primo(k)) { return k; } } // no factors found return 1; } 

类似地，对于primo方法，只要找到因子，就可以返回false 。

Answer 5

这是af＃版本：

 let lpf n = let rec loop n = function |k when k*k >= n -> n |k when n % k = 0I -> loop (n/k) k |k -> loop n (k+1I) loop n 2I