C# 寻找素数的程序

Program to find prime numbers

提问by sandy101

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

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

The program is

该程序是

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?

任何人都可以帮我找出程序中可能存在的错误吗？

采纳答案by SLaks

You can do this faster using a nearly optimaltrial 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; 
    }
);

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

这里使用的素数数量的近似公式是π(x) < 1.26 x / ln(x)。我们只需要通过不大于 的素数进行测试x = sqrt(num)。

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

请注意，Eratosthenes的筛选具有比试除法更好的运行时间复杂度（num如果正确实施，对于更大的值应该运行得更快）。

回答by whatnick

Smells like more homework. My very very old graphing calculator had a is prime program like this. Technnically the inner devision checking loop only needs to run to i^(1/2). Do you need to find "all" prime numbers between 0 and L ? The other major problem is that your loop variables are "int" while your input data is "long", this will be causing an overflow making your loops fail to execute even once. Fix the loop variables.

闻起来像更多的家庭作业。我非常非常古老的图形计算器有一个像这样的主要程序。从技术上讲，内部设备检查循环只需要运行到 i^(1/2)。您是否需要在 0 和 L 之间找到“所有”质数？另一个主要问题是您的循环变量是“int”，而您的输入数据是“long”，这将导致溢出，使您的循环甚至无法执行一次。修复循环变量。

回答by Cade Roux

Try this:

尝试这个：

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

回答by Guillermo Phillips

You only need to check odd divisors up to the square root of the number. In other words your inner loop needs to start:

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

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

You can also break out of the function as soon as you find the number is not prime, you don't need to check any more divisors (I see you're already doing that!).

您也可以在发现数字不是质数时立即跳出该函数，您无需再检查除数（我知道您已经在这样做了！）。

This will only work if num is bigger than two.

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

No Sqrt

无平方

You can avoid the Sqrt altogether by keeping a running sum. For example:

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

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

This is because the sum of numbers 1+(3+5)+(7+9) will give you a sequence of odd squares (1,9,25 etc). And hence jrepresents the square root of square_sum. As long as square_sumis less than ithen jis less than the square root.

这是因为数字 1+(3+5)+(7+9) 的总和会给你一个奇数平方序列（1,9,25 等）。因此j代表 的平方根square_sum。只要square_sum小于i则j小于平方根。

回答by Gordon Mackie JoanMiro

Very similar - from an exercise to implement Sieve of Eratosthenes in C#:

非常相似 - 来自在 C# 中实现 Eratosthenes 筛分的练习：

public class PrimeFinder
{
    readonly List<long> _primes = new List<long>();

    public PrimeFinder(long seed)
    {
        CalcPrimes(seed);
    }

    public List<long> Primes { get { return _primes; } }

    private void CalcPrimes(long maxValue)
    {
        for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
        {
            if (IsPrime(checkValue))
            {
                _primes.Add(checkValue);
            }
        }
    }

    private bool IsPrime(long checkValue)
    {
        bool isPrime = true;

        foreach (long prime in _primes)
        {
            if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
            {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
}

回答by Jeff

It may just be my opinion, but there's another serious error in your program (setting aside the given 'prime number' question, which has been thoroughly answered).

这可能只是我的意见，但您的程序中存在另一个严重错误（搁置已彻底回答的给定“质数”问题）。

Like the rest of the responders, I'm assuming this is homework, which indicates you want to become a developer (presumably).

像其他响应者一样，我假设这是家庭作业，这表明您想成为一名开发人员（大概）。

You need to learn to compartmentalize your code. It's not something you'll always need to do in a project, but it's good to know how to do it.

你需要学会划分你的代码。这不是你在项目中总是需要做的事情，但知道如何去做是件好事。

Your method prime_num(long num) could stand a better, more descriptive name. And if it is supposed to find all prime numbers less than a given number, it should return them as a list. This makes it easier to seperate your display and your functionality.

您的方法 prime_num(long num) 可以采用更好、更具描述性的名称。如果它应该找到小于给定数字的所有素数，它应该将它们作为列表返回。这样可以更轻松地分离您的显示器和您的功能。

If it simply returned an IList containing prime numbers you could then display them in your main function (perhaps calling another outside function to pretty print them) or use them in further calculations down the line.

如果它只是返回一个包含素数的 IList，那么你可以在你的主函数中显示它们（也许调用另一个外部函数来漂亮地打印它们）或者在后续的进一步计算中使用它们。

So my best recommendation to you is to do something like this:

所以我对你最好的建议是做这样的事情：

public void main(string args[])
{
    //Get the number you want to use as input
    long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments

    IList<long> primes = FindSmallerPrimes(number);

    DisplayPrimes(primes);
}

public IList<long> FindSmallerPrimes(long largestNumber)
{
    List<long> returnList = new List<long>();
    //Find the primes, using a method as described by another answer, add them to returnList
    return returnList;
}

public void DisplayPrimes(IList<long> primes)
{
    foreach(long l in primes)
    {
        Console.WriteLine ( "Prime:" + l.ToString() );
    }
}

Even if you end up working somewhere where speration like this isn't needed, it's good to know how to do it.

即使你最终在不需要这样的分散的地方工作，知道如何去做也是很好的。

回答by Jerry Coffin

People have mentioned a couple of the building blocks toward doing this efficiently, but nobody's really put the pieces together. The sieve of Eratosthenesis a good start, but with it you'll run out of memory longbefore you reach the limit you've set. That doesn't mean it's useless though -- when you're doing your loop, what you really care about are prime divisors. As such, you can start by using the sieve to create a base of prime divisors, then use those in the loop to test numbers for primacy.

人们已经提到了有效地做到这一点的几个组成部分，但没有人真正将这些部分放在一起。Eratosthenes的筛子是一个好的开始，但是使用它你会在达到你设置的限制之前很久就耗尽内存。但这并不意味着它没用——当你在做你的循环时，你真正关心的是质数除数。因此，您可以首先使用筛选器创建素数除数的基数，然后使用循环中的那些来测试数字的素数。

When you write the loop, however, you really do NOT want to us sqrt(i) in the loop condition as a couple of answers have suggested. You and I know that the sqrt is a "pure" function that always gives the same answer if given the same input parameter. Unfortunately, the compiler does NOT know that, so if use something like '<=Math.sqrt(x)' in the loop condition, it'll re-compute the sqrt of the number every iteration of the loop.

然而，当你编写循环时，你真的不希望我们在循环条件中使用 sqrt(i) ，正如一些答案所建议的那样。你我都知道 sqrt 是一个“纯”函数，如果给定相同的输入参数，它总是给出相同的答案。不幸的是，编译器不知道这一点，所以如果在循环条件中使用类似 '<=Math.sqrt(x)' 的东西，它会在循环的每次迭代中重新计算数字的 sqrt。

You can avoid that a couple of different ways. You can either pre-compute the sqrt before the loop, and use the pre-computed value in the loop condition, or you can work in the other direction, and change i<Math.sqrt(x)to i*i<x. Personally, I'd pre-compute the square root though -- I think it's clearer and probably a bit faster--but that depends on the number of iterations of the loop (the i*imeans it's still doing a multiplication in the loop). With only a few iterations, i*iwill typically be faster. With enough iterations, the loss from i*ievery iteration outweighs the time for executing sqrtonce outside the loop.

您可以通过几种不同的方式来避免这种情况。您可以在循环之前预先计算 sqrt，并在循环条件中使用预先计算的值，或者您可以在另一个方向工作，并更改i<Math.sqrt(x)为i*i<x. 就我个人而言，我会预先计算平方根——我认为它更清晰，可能更快一点——但这取决于循环的迭代次数（这i*i意味着它仍在循环中进行乘法运算）。只需几次迭代，i*i通常会更快。通过足够的迭代，i*i每次迭代的损失超过sqrt在循环外执行一次的时间。

That's probably adequate for the size of numbers you're dealing with -- a 15 digit limit means the square root is 7 or 8 digits, which fits in a pretty reasonable amount of memory. On the other hand, if you want to deal with numbers in this range a lot, you might want to look at some of the more sophisticated prime-checking algorithms, such as Pollard's or Brent's algorithms. These are more complex (to put it mildly) but a lotfaster for large numbers.

这对于您正在处理的数字的大小来说可能已经足够了——15 位限制意味着平方根是 7 或 8 位，这适合相当合理的内存量。另一方面，如果您想大量处理这个范围内的数字，您可能需要查看一些更复杂的素数检查算法，例如Pollard 或 Brent 算法。这些更复杂（委婉地说），但对于大数字来说要快得多。

There are other algorithms for even bigger numbers (quadratic sieve, general number field sieve) but we won't get into them for the moment -- they're a lot more complex, and really only useful for dealing with really big numbers (the GNFS starts to be useful in the 100+ digit range).

对于更大的数字，还有其他算法（二次筛、一般数域筛），但我们暂时不会讨论它们——它们要复杂得多，而且实际上只对处理非常大的数字有用（ GNFS 开始在 100+ 位范围内有用）。

回答by Ayhan ARICAN

Prime Helper very fast calculation

Prime Helper 计算速度非常快

public static class PrimeHelper
{

    public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
    {
        return (new PrimesInt32(maxNumber));
    }

    public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
    {
        return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
    }

    public static bool IsPrime(this Int64 number)
    {
        if (number < 2)
            return false;
        else if (number < 4 )
            return true;

        var limit = (Int32)System.Math.Sqrt(number) + 1;
        var foundPrimes = new PrimesInt32(limit);

        return !foundPrimes.IsDivisible(number);
    }

    public static bool IsPrime(this Int32 number)
    {
        return IsPrime(Convert.ToInt64(number));
    }

    public static bool IsPrime(this Int16 number)
    {
        return IsPrime(Convert.ToInt64(number));
    }

    public static bool IsPrime(this byte number)
    {
        return IsPrime(Convert.ToInt64(number));
    }
}

public class PrimesInt32 : IEnumerable<Int32>
{
    private Int32 limit;
    private BitArray numbers;

    public PrimesInt32(Int32 limit)
    {
        if (limit < 2)
            throw new Exception("Prime numbers not found.");

        startTime = DateTime.Now;
        calculateTime = startTime - startTime;
        this.limit = limit;
        try { findPrimes(); } catch{/*Overflows or Out of Memory*/}

        calculateTime = DateTime.Now - startTime;
    }

    private void findPrimes()
    {
        /*
        The Sieve Algorithm
        http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
        */
        numbers = new BitArray(limit, true);
        for (Int32 i = 2; i < limit; i++)
            if (numbers[i])
                for (Int32 j = i * 2; j < limit; j += i)
                     numbers[j] = false;
    }

    public IEnumerator<Int32> GetEnumerator()
    {
        for (Int32 i = 2; i < 3; i++)
            if (numbers[i])
                yield return i;
        if (limit > 2)
            for (Int32 i = 3; i < limit; i += 2)
                if (numbers[i])
                    yield return i;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    // Extended for Int64
    public bool IsDivisible(Int64 number)
    {
        var sqrt = System.Math.Sqrt(number);
        foreach (var prime in this)
        {
            if (prime > sqrt)
                break;
            if (number % prime == 0)
            {
                DivisibleBy = prime;
                return true;
            }
        }
        return false;
    }

    private static DateTime startTime;
    private static TimeSpan calculateTime;
    public static TimeSpan CalculateTime { get { return calculateTime; } }
    public Int32 DivisibleBy { get; set; }
}

回答by sujeetpasi

    public static void Main()
    {  
        Console.WriteLine("enter the number");
        int i = int.Parse(Console.ReadLine());

        for (int j = 2; j <= i; j++)
        {
            for (int k = 2; k <= i; k++)
            {
                if (j == k)
                {
                    Console.WriteLine("{0}is prime", j);

                    break;
                }
                else if (j % k == 0)
                {
                    break;
                }
            }
        }
        Console.ReadLine();          
    }

回答by sujeetpasi

static void Main(string[] args)
    {  int i,j;
        Console.WriteLine("prime no between 1 to 100");
    for (i = 2; i <= 100; i++)
    {
        int count = 0;
        for (j = 1; j <= i; j++)
        {

            if (i % j == 0)
            { count=count+1; }
        }

        if ( count <= 2)
        { Console.WriteLine(i); }


    }
    Console.ReadKey();

    }