-1

我编写了以下代码来计算和输出素数。

我得到的素数在控制台上输出并存储在文本文件中。

它计算直到指定的所有数字。

有关使此代码运行得更快、更有效的任何建议？

    static void Main(string[] args)
    {
        long i;
        long j;    

           for (i = 3; i < 10000000; i += 2)
           {
               bool isPrime = true;

               for (j = 2; j <= i / 2; j++)
               {
                   if (i % j == 0)
                   {
                       isPrime = false;
                       break;
                   }
               }

               if (isPrime)
               {
                   Console.WriteLine(i);

                   using (System.IO.StreamWriter StreamWriter = System.IO.File.AppendText(@"C:\Users\Marco\Documents\Visual Studio 2012\Projects\Prime Number Generator\Prime Number Generator\bin\Debug\Prime List.txt"))
                   {
                       StreamWriter.WriteLine(i);
                   }
               }
           }
    }

谢谢

4

3 回答 3

1

您使用的算法称为试除法，如果您按照@sashkello 和@giuliofranco 的建议在平方根处停止，它的时间复杂度为 O(n^2) 或 O(n^1.5)。更好的算法是两千多年前发明的埃拉托色尼筛法，时间复杂度为 O(n log log n)，接近 O(n)。埃拉托色尼筛法首先列出从 2 到最大所需素数n的所有数字，然后进入迭代阶段。在每一步，然后确定尚未考虑的最小未交叉数，并删除该数的所有倍数；重复此操作，直到没有未交叉的数字未被考虑。所有未交叉的数字都是素数。

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] := False

在primes函数中，是数字列表，未交叉的数字在issieve时按升序考虑，并且在考虑时作为素数输出，倍数的“交叉”由i上的循环完成；循环开始是因为所有较小的倍数已经被较小的素数划掉了。sieve[p]Truep*p

如果你对使用素数编程感兴趣，我在我的博客中谦虚地推荐这篇文章，它讨论了这个算法，给出了一个可以使其速度加倍的优化，提供了许多其他关于素数的算法，并提供了五种语言的实现。

于 2013-08-06T02:45:35.257 回答
1

  1. 您只需要检查除法sqrt(i)，而不是i/2。（正如@I4V 在下面的评论中适当指出的那样，j*j < i将比j < sqrt(i)平方根是一个非常慢的运算 cmp 更快。乘法）

  2. 您可以在循环中使用以前找到的素数（即，将它们存储在数组中并循环遍历它们），因为您只需要检查素数的可分性。

只有在你优化了算法之后，才开始优化你的代码。

于 2013-08-05T23:48:29.393 回答
0

1) 在 sqrt(i) 处结束循环，而不是 (i/2)。您节省的时间值得您计算平方根所需的时间。

2）不要只是忘记你生成的数字。将它们保存到一个数组中（至少是最后一个），然后尝试仅将您的候选人除以您知道是素数的数字。如果 x%y==0，则要么 y 是素数，要么存在素数 P<y，因此 x%P==0。并且小于 i 的素数大约只有 i/ln(i)。这意味着当您已经可以得到所有小于 i 的素数时，您正在浪费时间测试所有数字。请注意，如果你这样做，你的 RAM 会更重。

static void Main(string[] args)
{
    long i;
    int j;
    List<long> primes = new List<long>();
    primes.Add(2);
    long maxJ;

    using (System.IO.StreamWriter StreamWriter = System.IO.File.AppendText(@"C:\Users\Marco\Documents\Visual Studio 2012\Projects\Prime Number Generator\Prime Number Generator\bin\Debug\Prime List.txt"))
    {
        for (i = 3; i < 10000000; i += 2)
        {
            //Compute only once, rather that at each iteration
            maxJ = (long)Math.Sqrt(i);
            for (j = 0; j < primes.Count && primes[j] <= maxJ; ++j)
            {
                if (i % primes[j] == 0)
                {
                    goto EndOfOuterLoop;
                }
            }

            Console.WriteLine(i);
            StreamWriter.WriteLine(i);
            primes.Add(i);

            EndOfOuterLoop:
        }
    }
}

3）如果你真的想要最大可达到的速度，你应该使用AKS或Miller-Rabin算法，它可以检查一个数是否在多项式时间内是素数（AKS总是正确的，Miller-Rabin有时可以说一个非素数数是素数）。

于 2013-08-06T02:29:56.813 回答