计划找素数 [英] Program to find prime numbers

问题描述

我想找到和0的素数很长的变量，但我不能让任何输出。

I want to find the prime number between 0 and a long variable but I am not able to get any output.

该计划是

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

任何一个可以帮助我找到的是在节目中可能出现的错误？

Can any one help me out and find what is the possible error in the program?

推荐答案

您可以用做快的近最优的审判庭筛在一个（长）线是这样的：

You can do this faster using a nearly optimal trial division sieve in one (long) line like this:

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） ＆LT; 1.26 X / LN（X） 的。我们只需要通过素数不超过的 X =开方（NUM） 的

The approximation formula for number of primes used here is π(x) < 1.26 x / ln(x). We only need to test by primes not greater than x = sqrt(num).

需要注意的是埃拉托色尼的筛具有更好的运行时间复杂度比审判庭（应为更大的运行得更快 NUM 的值，当正确实施）。

Note that the sieve of Eratosthenes has much better run time complexity than trial division (should run much faster for bigger num values, when properly implemented).

这篇关于计划找素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！