程序中循环查找素数的问题

Question

您好，我一直无法解决如何让它工作的问题。它是旨在使用用户输入设置 x 来查找前 x 个素数。然后它将在打印结果之前将 any 放入数组中。我认为我对循环提出了一个问题，因为一旦输入用户输入，什么都不会发生。如果有人能指出我出错的地方并提供有关如何修复它的建议，我将不胜感激。谢谢

static void Main(string[] args)
    {
        int max, i, count;
        i = 0; // this is used to keep trck of how many primes have been added to the array
        count = 0; // this is used to test each number
        Console.WriteLine("This will work out the first x prime numbers with x being the number of prime numbers you want");
        Console.WriteLine("Enter the number of prime numbers you want.");
        max = Convert.ToInt32(Console.ReadLine());

        int[] primes = new int[max];

        while (i <= max)
        {
         while (count <= 9999)
         {
             if (count % 2 == 0 || count % 3 == 0 || count % 5 == 0 || count % 7 == 0 ) // tests if count number is a prime 
             {
                 if (count == 2 || count == 3 ||count == 5 ||count == 7 ) // ensures 2,3,5,7 are added to primes if neccesarry
                 {

                     primes[count] = count; //add to array
                     i++; // increments the count on the number of prime numbers
                 }
                 count ++; // increments the count 
                 break;
             }
             else
             {
                 primes[count] = count;
                 i++;
                 count ++;
             }
         }
        }

        Console.WriteLine("The first {0} prime numbers are ... ", max);
        foreach(var item in primes)
        {
            Console.Write(item.ToString() + ", ");
        }
    }

Answer 1

首先，这不是检验一个数是否为质数的方法，但话又说回来，循环是完全错误的。

如果你设置的最大值大于小于 9999 的素数，它将永远在外循环中循环。

查看 wiki 以获得一些初步见解：http://en.wikipedia.org/wiki/Primality_test

要检查我的陈述，您可以在外循环中添加一些控制台输出并亲自查看

Answer 2

本着尽量保持原始代码的精神，这里对您的算法进行了调整，修改为使用 Sieve of Eratosthenes:

Sieve 可以迭代确定所有素数，仅需知道 2 是素数。
内部循环的退出条件应该是当我们超过我们正在测试的数字的平方根时，我们的已知素数列表（不是 9999 和 break）。由于素数的定义，有了一个最多为 X 的素数列表，我们可以解析所有其他最多为 X * X 的素数。（因此，如果我们超过平方根，我们可以停止测试，例如 2 可以解析 3 和4、2 和 3 最多可以解析 9，等等）。这也是因为我们的质数已经按升序排列了。
我保留了原始变量，即count是下一个测试的候选素数，i是素数的当前索引，max是要填充的上限。
第一个素数 2 需要硬编码（即 primes[0] = 2，下一个素数索引 i 将是 1，之后我们需要检查的第一个候选数将是 3 .

// We do need to hard code that 2 is a prime number. Everything else can be derived
primes[0] = 2;
i = 1;
count = 3;

// i.e. stop when we get the required number of primes
while (i < max)
{
    // Indicator to stop testing this candidate if we find a factor
    bool foundFactor = false;
    // Start off each primality test from the start of our primes array
    var primeIndex = 0;

    // Try and find a factor of 'count' with our known primes
    while (!foundFactor && primeIndex < i)
    {
        // We can stop after the square root. Multiplication is faster than sqrt
        if (primes[primeIndex]*primes[primeIndex] > count)
            break;
        // If the candidate number
        if (count % primes[primeIndex] == 0)
            foundFactor = true;
        primeIndex++;
    }
    if (!foundFactor)
    {
        primes[i] = count;
        i++;
    }

    count++;
}

根据@Massimo 的 link，上述蛮力机制效率极低。一个改进是维基文章中提到的'wheel of 6'——在count=6之后，6的轮子将每个候选数字集以6为一组进行测试，可以立即消除所有2和3的倍数.也可以使用其他更大的轮子。

程序中循环查找素数的问题

Trouble with loops in a program to find prime numbers

c#

loops

console-application

nested-loops