c# - 寻找质数的程序

Question

我想在 0 和一个 long 变量之间找到素数，但我无法获得任何输出。

程序是

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();
        }
    }
}

谁能帮我找出程序中可能存在的错误是什么？

Answer 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)的素数来测试.

请注意 sieve of Eratosthenes具有比试验除法更好的运行时间复杂性(如果实现得当，对于更大的 num 值应该运行得更快)。