C#中的Euler #3项目--最大素数因子

Question

我刚刚开始做欧拉挑战项目，现在我正在进行挑战#3 -- 600851475143的最大主要因素。

我编写了一些代码，并试图根据其他堆栈溢出用户的建议对其进行优化。

我得到的是这个代码，它的工作，但我认为它需要更长的时间，它应该-计算高的数字，如600851475143需要永远！

我走的路对吗？我怎么才能优化它？

using System;

namespace ProjectEuler_LargestPrimeFactor
{
    class Program
    {
        static long numberToFactor = 600851475143;

        static void Main(string[] args)
        {
            Console.WriteLine(LargestPrimeFactorOf(numberToFactor) + " is the largest prime factor of " + numberToFactor);
            Console.ReadKey();
        }

        static long LargestPrimeFactorOf(long n)
        {
            long lastPrimeFactor = 0;

            for (long i = 2; i < n; i++)
            {
                if (isPrime(i) && n % i == 0)
                {
                    lastPrimeFactor = i;
                    Console.WriteLine(i + " is a prime factor of " + n);
                }
            }

            return lastPrimeFactor;
        }

        static bool isPrime(long n)
        {
            if (n == 2) return true;
            if ((n > 2 && n % 2 == 0) || n == 1) return false;

            for (long i = 2; i <= Math.Floor(Math.Sqrt(n)); ++i)
            {
                if (n % i == 0) return false;
            }

            return true;
        }
    }
}

Answer 1

static bool isPrime(long n)
{
    if (n == 2) return true;
    if ((n > 2 && n % 2 == 0) || n == 1) return false;

    for (long i = 2; i <= Math.Floor(Math.Sqrt(n)); ++i)
    {
        if (n % i == 0) return false;
    }

    return true;
}

上述代码效率低下。

• 性能:由于n没有变化，所以您应该只计算√n一次。
• 性能:不要在for循环中检查偶数，因为它们永远不会均分。
• 可读性:不要将n == 1大小写与n is even大小写混为一谈。
• 命名:方法名以大写字母开头。

改进代码：

static bool IsPrime(long n)
{
    if (n < 4) return n > 1;
    if (n % 2 == 0 || n % 3 == 0) return false;

    long limit = (long) Math.Sqrt(n);
    for (long i = 5; i <= limit; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}

Answer 2

这是我对这个问题的解决办法

    static void Main(string[] args)
    {
        long num = 600851475143;
        int count = 3;
        Stopwatch sw = Stopwatch.StartNew();
        while (num > 1)
        {
            if (num%count == 0)
            {
                num /= count;
            }
            else
            {
                count += 2;
            }
        }
        sw.Stop();
        Console.WriteLine("The largest prime factor of the number {0} is {1} ", 600851475143, count);
        Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }

首先，您将在Project上找到的大部分练习都需要一些数学公式或概念，以达到最高的性能。这不是纯粹的编程，因此在我看来也不是最好的练习地方(ofc假设你不知道所有的公式)，在这个过程中你可能会学到比编程更多的数学知识，如果这是你想要的，那是件好事。长话短说，在开始编程之前，先寻找公式。

回到您的实际代码：

为什么您的代码工作缓慢？这里有几点我想要做的是，第一个方法调用比单个方法中的一堆代码慢一些问题，稍后您会在Project中发现一些问题很容易解决，但是很难优化，所以通常的C#代码在方法和类中都是分离的，因为在一个正常的项目中，性能损失并不大，但是在某些情况下，这可能是唯一的瓶颈。你应该总是从长远的角度来思考，如果你有更多的数字呢？你的方法还能用得够快吗？一个有效的程序并不意味着它是一个好的程序。

接下来，你开始思考你能改进什么，以及为什么你在做某些事情。你真的需要知道每一个素数吗？

在我的解中，有一个简单的素数分解，从最小素数开始，我们不断地增加我们现有的数，直到我们得到一个只能自己除以的数，即最大素数因子。100,000次迭代在我的机器上运行了大约3000到3200毫秒。

Answer 3

小调

static bool isPrime(long n)
{
    if (n < 2)      return false;
    if (n <= 3)     return true;
    if (n % 2 == 0) return false;

这是不对的

for (long i = 2; i <= Math.Floor(Math.Sqrt(n)); ++i)

你应该从5开始跳到2

请参阅维基

function is_prime(n : integer)
if n ≤ 1
    return false
else if n ≤ 3
    return true
else if n mod 2 = 0 or n mod 3 = 0
    return false
let i ← 5
while i×i ≤ n
    if n mod i = 0 or n mod (i + 2) = 0
        return false
    i ← i + 6
return true;

我在一条评论中向丹尼斯指出了偶数的问题，但他拒绝对他的答案做一个简单的修正。

解决方案：

long num = 600851475143;
long sqrt = (int)Math.Sqrt(num);
long count = 2;
while (num > 1)
{
    if (num % count == 0)
        num /= count;
    else
    {
        count ++;
        if(count % 2 == 0)
            count ++;
        if(count > 3 && count % 3 == 0)
            count += 2;
        if (count > sqrt)
        {
            Console.WriteLine("number is prime ignore following line");
            break; // num is a prime
        }
    }
}
Console.WriteLine("The largest prime factor of the number {0} is {1} ", num, count);
Console.ReadLine();