c# - 我的程序是否花费了太多时间来执行？

Question

我想解决来自 project euleur 的一个关于找到一个大数的最大素数的问题。我在 Visual Studio 2012 的虚拟机上运行我的代码，代码似乎冻结了。当我进入循环时，代码运行良好，但是当我执行它时，控制台总是在那里。就好像程序仍在运行一样。会不会是程序需要时间来执行？

我的代码

static void Main(string[] args)
{
    long number = 5;

    for (long i = 1; i < 600851475143; i++)
    {
        if (i % 2 != 0 && i % 1 == 0 && i % i == 0)
            number = i;
    }

}

Answer 1

我运行了这段代码，它确实需要一段时间才能运行，但它似乎确实在进步（我确实增加了）。试试这个来确定 i 是否是素数：

    public static bool IsPrime(long candidate)
    {
        // Test whether the parameter is a prime number.
        if ((candidate & 1) == 0)
        {
            return candidate == 2;
        }
        // Note:
        // ... This version was changed to test the square.
        // ... Original version tested against the square root.
        // ... Also we exclude 1 at the very end.
        for (int i = 3; (i * i) <= candidate; i += 2)
        {
            if ((candidate % i) == 0)
            {
                return false;
            }
        }
        return candidate != 1;
    }

我不能为此声称功劳。它来自http://www.dotnetperls.com/prime。

将一些 Console.WriteLines 添加到您的 main 方法中以使其进度：

    static void Main(string[] args)
    {
        long number = 5;

        for (long i = 1; i < 600851475143; i++)
        {
            if (IsPrime(i))
            {
                Console.WriteLine(i);
                number = i;
            }
        }
    }

这些算法还有其他资源：http: //csharpinoneroom.blogspot.com/2008/03/find-prime-numer-at-fastest-speed.html

祝你好运！

Answer 2

你的算法不正确。以下是一种适用于 Project Euler 的求合数素因数的简单方法：

function factors(n)
    f := 2
    while f * f <= n
        if n % f == 0
            output f
            n := n / f
        else
            f := f + 1
    output n

这通过连续将n除以每个f来工作，每当找到一个素因子时，减少n并输出f 。最后一个因素是当f大于 n 的平方根时剩余的n，此时n必须是素数。

还有其他方法可以分解整数。当你准备好更多时，我谦虚地在我的博客上推荐这篇文章。

Answer 3

最终，如果它不能正常工作，你是否编写世界上最快的代码也没关系。你的没有，抛开速度。