C#,找到一个数字的最大素数因子

Question

我是编程新手,我正在练习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个模运算.

这里有更新的优化版本