如何生成用户定义数量的质数？

Question

我正在尝试根据用户输入生成质数。这是我目前的代码，但我似乎无法解决它：

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for

- Covertpyro

---

你遇到的确切问题是什么？你得到了错误的结果吗？合数？数字不够？ - a_m0d

我认为我的第一个for循环没有正确处理用户定义的部分。它输出2，然后是23，然后是235等。 - Covertpyro

Answer 1

如果你查看你的循环结构，你应该能够很容易地看出为什么你的结果是错误的。手动逐步执行它们（这不会花费很长时间）。

产生当前结果的原因是，外部循环（`x < numberOfPrimes`）并不会产生每次迭代的结果——由于内部循环的结构方式，它将跳过相当多的迭代。

你真正需要做的是重新构造内部循环。你的最内层循环运行良好，应该检测任何质数。然而，你的第二个循环应该只测试尚未经过测试的数字。此外，一旦找到质数，它就应该停止循环。

- a_m0d

---

我发现我只是无法弄清楚如何构建它。 - Covertpyro

我不想直接给出答案，因为 a_m0d 正试图让你自己解决问题，但是这里有另一个提示：你需要摆脱外部循环（你只需要从2开始计数一次）。 - Jimmy

@Jimmy - 外层循环是为了生成足够的数字。还有其他方法可以做到这一点，但这是他的结构，我只是在帮助他使他的结构对他起作用。 - a_m0d

当我将其更改为a <= 100时，它会运行到100的质数并根据我输入的numberOfPrimes多次打印它们。我认为我需要删除第一个for循环。 - Covertpyro

我去掉了第一个循环，添加了变量“count”，将剩余的最外层循环改为count < numberOfPrimes，并在if语句中添加了一个增量器，如果测试为质数，则显示该数字。 - Covertpyro

Answer 2

你应该更好地组织你的代码，现在它非常混乱。有一个方法IsPrime(int x)，如果x是素数则返回true，否则返回false。

然后，要生成numberOfPrimes个素数，你可以这样做：

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

或者使用埃拉托斯特尼筛法，这是一种更快的方法。

要确定一个数字x是否为质数，请尝试在2和Sqrt(x)之间尝试所有因子。为什么只有Sqrt(x)？因为如果a*b=x，那么x/b=a和x/a=b，所以你会检查两次所有东西，而且如果你到达x/2甚至x，你还会检查不应该检查的东西。

所以如果您想使用IsPrime(x)函数，可以像这样：

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

但是我建议您使用埃拉托斯特尼筛法，因为它要快得多。您还可以优化一些东西，以便不检查偶数，因为偶数除了2之外都不是素数（在筛法和朴素方法中都是如此）。将x = 2视为边缘情况，然后开始检查每个其他数字（3、5、7、9、11等）

- IVlad

---

一个数也是质数当它没有质因子；检查x是否被小于sqrt(x)的质数整除比检查x是否被任何小于sqrt(x)的数整除要快得多。所以你确实想要将一个质数列表传递给你的'IsPrime'函数... - Kirk Broadhurst

没错，但是你可以使用埃拉托色尼筛算法。你说的没错，确实有速度上的好处，但它只是在优化一种天真的解决方案，而这种方法比起使用列表和筛法来说还是不够优越的。如果你想得到最好的算法，就应该使用筛法。 - IVlad

Answer 3

下一个质数（x）是不能被所有小于等于sqrt（x）的质数s整除的数字。因此，您可以使用类似以下的函数：

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

然后你就可以得到质数，如下：

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);

- Steck

---

还可以将“2”作为预定义质数添加，并仅检查奇数。 - Steck

Answer 4

var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

从codethinked.com复制

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

    for (int i = 3; i < m; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}

- Pratik Deoghare

---

看起来不错，但从学习编写质数算法的角度来看，这并不是一个好的作业答案。 - Kirk Broadhurst

这个代码只列出了小于等于numberOfPrimes的质数，不是列出numberOfPrimes个质数。无论如何，你应该避免使用sqrt方法，它非常慢。 - IVlad

我认为OP并不是在问“请把一堆代码复制粘贴到这里”。他是在问“这是我的代码，请帮我修复它”。 - Kirk Broadhurst

我认为这段代码可以帮助他识别代码中的问题。非常抱歉，但我有点忙，匆忙地粘贴了所有可用的内容。 - Pratik Deoghare

Answer 5

1. 重命名你的变量。

首先，如果这是作业，你会得到不好的成绩（如果你的老师很有水平），因为你的变量名没有意义（是的，即使是numberOfPrimes也是错误的，应该被命名为requiredNumberOfPrimes。当我看到这个变量时，我会问自己“这是他想要的数量还是他已经找到的数量？”）。

其次，这将帮助你理解你做错了什么。变量应该根据它们所代表的内容进行逻辑命名。如果你不能解释你的变量代表什么（例如a和b），那么你可能无法解释你正在做什么。

2. 查看你的循环。

for (int x = 0; x < numberOfPrimes; x++)

for循环的结构是(初始化; '是否继续?'; '每次循环执行这个')。因此在你的循环中

• 你会一直继续，直到x等于或大于numberOfPrimes*
• 每次循环时，你都会将1添加到x。

你确定这是你想要做的吗？x似乎代表你找到的质数数量。那么为什么不在找到质数时递增它，而不是在开始循环时递增呢？

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

您正在查看介于2和x之间的每个整数，包括2和x。对于这些整数中的每一个整数a，您都在查看介于a和2之间的每个整数。您将如何处理这些整数？

每次循环通过您的顶级循环（x循环）时，您都将从头开始执行a循环，并且每次循环通过a循环时，您都将从头开始执行b循环。

因此，如果x为10，则首先运行一次a（a=2），然后再次运行a（a=2，a=3），然后再次运行a（a=2，a=3，a=4），然后......

3. 收集结果而不是将其写入控制台。

var primes = new List<int>();

这很容易。当你找到一个质数时，primes.Add(a);。然后你就知道你已经找到了多少个质数（primes.Count），你可以使用质数列表高效地确定下一个质数，如果需要的话，以后还可以使用该列表。

- Kirk Broadhurst

Answer 6

一旦你解决了循环问题，你只需要检查b < sqrt(a)，如果更高的话，你会先找到另一个因子。

- Spike

---

嗯，他明确地标记了它是作业，所以我认为这是一份作业。 - a_m0d

哦，是的。又到了眼科医生的时间了。 - Spike

Answer 7

你所需要的是“埃拉托斯特尼筛法”。由于我不想帮助别人完成作业，这是我唯一能给你的提示。这个算法在互联网上很容易找到。

- Muad'Dib

---

这并不是他的问题 - 只需稍微重构一下他的算法就可以生成质数。好吧，这可能不是最高效的算法，但它能够工作。 - a_m0d

好的，没错，但如果他知道要搜索什么，他可能会找到示例代码。 - Muad'Dib