检查素数

Question

我需要制作一个 GUI 应用程序，在用户输入两个数字时检查质数。标准是我制定了两种方法，一种检查 一个数字是否为质数 ，这是我的 isPrime(int n)，另一种检查两个输入中的哪一个是 lower/higher 以便程序知道从哪里开始。

我做不到。当我运行脚本时，我在列表框中没有任何输出。

到目前为止我的代码：

private void button1_Click(object sender, EventArgs e)
{
    int num1, num2;
    num1 = Int32.Parse(textBox1.Text);
    num2 = Int32.Parse(textBox2.Text);

    for (int i = num1; i <= num2; i++) //Method that checks which of the two inputs is lower/hihger
    {
        if (isPrime(i))
        {
            for (int j = 2; j <= 1 / 2; j++)
            {
                if (i % j == 0)
                {
                    break;
                }
            }
            if (i == 0 && i != 1)
            {
                listBox1.Items.Add(i);
            }
        }
    }
}

private static bool isPrime(int n) //Method to check prime numbers
{
    for (int i = 2; i < n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

Answer 1

您的 isPrime 函数是正确的，您需要做的小改动是将 i <= Math.Sqrt(n) 的条件更新为 for (int i = 2; i <= Math.Sqrt(n); i++)。那会更多efficient。 Sieve of Eristhostenes.

您也可以参考以下链接找到更好更有效的检查方法isPrime。正如 @Fildor 在评论中所建议的那样。

Program to find prime numbers

要从两个输入中找到 min 或 max 值，请使用 Math.Min & Math.Max，如下所示。并更新您的 for 循环如下。

private void button1_Click(object sender, EventArgs e)
{
    int num1, num2;
    num1 = Math.Min(Int32.Parse(textBox1.Text), Int32.Parse(textBox2.Text));
    num2 = Math.Max(Int32.Parse(textBox1.Text), Int32.Parse(textBox2.Text));

    for (int i = num1; i <= num2; i++) //Method that checks which of the two inputs is lower/hihger
    {
        if (i != 0 && i != 1 && isPrime(i))
        {               
            listBox1.Items.Add(i);
        }
    }
}

private static bool isPrime(int n) //Method to check prime numbers
{
    for (int i = 2; i <= Math.Sqrt(n); i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

Answer 2

让我们从isPrime开始。由于它以 int n 作为参数，因此 n 最多可以达到 int.MaxValue ~ 2_000_000_000； 20 亿 次迭代有点太多了，因为我们可以轻松地只用 sqrt(2_000_000_000) / 2 ~ 30_000 循环实现一个例程：

    private static bool isPrime(int n) {
      if (n <= 1)
        return false;
      else if (n % 2 == 0)
        return n == 2;

      int max = (int)(Math.Sqrt(n) + 0.5);

      for (int divisor = 3; divisor <= max; divisor += 2)
        if (n % divisor == 0)
          return false;

      return true;   
    }

现在，是时候获取 num1 和 num2 之间的素数了：

    for (int i = num1; i <= num2; ++i)
      if (isPrime(i))
        listBox1.Items.Add(i);

请注意，由于我们优化了 isPrime，我们可以使 for 循环非常简单。

Answer 3

只是为问题添加另一种观点：

我根本不会在此处检查（如“计算”中的）素数。

Int32 包含相当有限数量的素数，这使我们可以预先计算或者如果可以找到一个列表，甚至可以从互联网上下载一个列表。

一旦我们有了它，您需要做的就是查找恰好在所需范围内的那些。

检查素数

Check prime numbers

c#

primes