程序查找素数

一尘不染

程序查找素数

我想找到介于0和一个长变量之间的质数，但我无法获得任何输出。

该程序是

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication16
{
    class Program
    {
        void prime_num(long num)
        {
            bool isPrime = true;
            for (int i = 0; i <= num; i++)
            {
                for (int j = 2; j <= num; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    Console.WriteLine ( "Prime:" + i );
                }
                isPrime = true;
            }
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            p.prime_num (999999999999999L);
            Console.ReadLine();
        }
    }
}

谁能帮助我，找出程序中可能出现的错误？

阅读 343

2020-05-19

共1个答案

一尘不染

您可以在一条（长）行中使用 接近最佳的 试验分割筛来更快地完成此操作，如下所示：

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

此处使用的素数的近似公式为 π(x)< 1.26 x / ln(x)。我们只需要测试不大于的素数即可 x = sqrt(num) 。

请注意，Eratosthenes筛的运行时复杂度比试验分割要好得多（
num 正确实施时，对于较大的值，其运行速度应更快）。

2020-05-19