寻找素数的程序

Question

寻找素数的程序我想找到介于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();         }     }}任何人都可以帮助我找出程序中可能出现的错误吗？

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)。

请注意，Eratosthenes的筛网比试验分区具有更好的运行时间复杂度（num如果正确实施，应该更快地运行更大的值）。

Answer 2

试试这个：

void prime_num(long num){

    // bool isPrime = true;
    for (long i = 0; i <= num; i++)
    {
        bool isPrime = true; // Move initialization to here
        for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
        {
            if (i % j == 0) // you don't need the first condition
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            Console.WriteLine ( "Prime:" + i );
        }
        // isPrime = true;
    }}

Answer 3

您只需要检查奇数除数，直到数字的平方根。换句话说，你的内循环需要开始：

for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }

一旦发现数字不是素数，你也可以打破这个功能，你不需要检查任何更多的除数（我看你已经这样做了！）。

这仅在num大于2时才有效。

没有Sqrt

您可以通过保持运行总和来完全避免Sqrt。例如：

int square_sum=1;for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}

这是因为数字1+（3 + 5）+（7 + 9）的总和将给出一系列奇数正方形（1,9,25等）。因此j代表了平方根square_sum。只要square_sum不到i那么j小于平方根。