寻找素数的C程序

问题描述 投票：0回答：5

我编写了一个 C 程序，它可以判断给定的数字是否是素数。但它有一个问题。对于 5 的倍数以外的数字，它工作得很好。但它会将 5 的倍数显示为素数，例如 15、25、35、45...。我无法找到错误。我尝试将它与互联网上的其他程序进行比较，但我无法找到错误。

#include <stdio.h>

int primeornot(int a) {
    int i;

    for (i = 2; i <= a / 2; i++) {
        if (a % i == 0) {
            return 0;
            break;
        } else {
            return 1;
        }
    }
}

main() {
    int number_given_by_user;

    printf("Enter a positive integer to find whether it is prime or not : ");
    scanf("%d", &number_given_by_user);

    if (primeornot(number_given_by_user)) {
        printf("The given number is a prime number");
    } else {
        printf("The given number is not a prime number");
    }
}
c function for-loop primes
5个回答
1
投票

不仅是 5 的倍数（例如，您的代码也将 9 视为素数）

您的代码有缺陷。您正在使用循环，但仅检查第一次迭代，因为循环内条件的每个分支内都有一个 

return
：

for(i=2;i<=a/2;i++)
{
    if(a % i == 0)
    {  
        return 0;    // <------- (this one is fine, since finding a divisor means outright that this number isn't a prime)
        break;       //  also, a break after a return is redundant
    }
    else
    {
        return 1;    // <------- (however, this one is flawed)
    }
}

在这种形式中，您的代码只执行

return !(input % 2)
，这不是一个很好的素数查找算法:-)

你需要做的是检查所有的迭代，只有当它们都进入

else
分支时，数字才是素数。

所以，改为：

int primeornot(int a)
{
int i;

for(i=2;i<=a/2;i++)
{
    if(a % i == 0)
    {
        return 0;
    }
    else
    {
        continue;
    }
}
return 1; // loop has ended with no divisors --> prime!!
}

或者，更好的是：

int primeornot(int a)
{
int i;

for(i=2;i<=a/2;i++)
{
    if(a % i == 0)
    {
        return 0;
    }
}
return 1; // loop has ended with no divisors --> prime!!
}
1
投票

函数

primeornot
在第一次测试后立即返回。您并没有按照您的预期测试每个除数直到 
a / 2
。

另请注意，测试直到 

a / 2
的每个数字都是浪费，您可以在 
i * i > a
时停止。

这是更正后的版本：

int primeornot(int a) {
    int i;

    for (i = 2; i * i <= a; i++) {
        if (a % i == 0) {
            return 0;
        }
    }
    return 1;
}

您可以通过测试 2 一次并且此后仅测试奇数来进一步改进功能：

int primeornot(int a) {
    int i;

    if (a != 2 && a % 2 == 0)
        return 0;

    for (i = 3; i * i <= a; i += 2) {
        if (a % i == 0) {
            return 0;
        }
    }
    return 1;
}

最后，不带参数的

main
的原型是
int main(void)
，你应该在消息后输出换行符并返回
0
：

int main(void) {
    int number_given_by_user;

    printf("Enter a positive integer to find whether it is prime or not: ");
    scanf("%d", &number_given_by_user);

    if (primeornot(number_given_by_user)) {
        printf("The given number is a prime number\n");
    } else {
        printf("The given number is not a prime number\n");
    }
    return 0;
}
0
投票

如果它不可整除，则返回，因此迭代只会在 for 循环中发生一次！因为无论如何你都会回来！下面的代码将适合你！

#include<stdio.h>

int primeornot(int a)
{
    int i;
    for(i=2;i<=a/2;i++)
    {
        if(a % i == 0)
        {
            return 0;
            break;
        }

    }
    return 1;
}

int main()
{
    int number_given_by_user;

    printf("Enter a positive integer to find whether it is prime or not : ");
    scanf("%d",&number_given_by_user);

    if(primeornot(number_given_by_user))
    {
        printf("The given number is a prime number");
    }
    else
    {
        printf("The given number is not a prime number");
    }
}
0
投票
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Is it Prime? Checking Numbers in C</title>
</head>
<body>
  <h1>Is it Prime? Checking Numbers in C</h1>
  <p>Prime numbers are the building blocks of number theory, and identifying them is a fundamental programming task. In C, we can write a program to efficiently check whether a given number is prime or not.</p>

  <h2>Code Breakdown</h2>
  <pre><code>
    #include &lt;stdio.h&gt;
    #include &lt;math.h&gt;

    int main() {
      int num, isPrime = 1;
      printf("Enter a positive integer: ");
      scanf("%d", &num);

      // Handle non-positive numbers
      if (num &lt;= 1) {
        isPrime = 0;
      } else {
        // Check for divisibility from 2 to sqrt(num)
        for (int i = 2; i &lt;= sqrt(num); i++) {
          if (num % i == 0) {
            isPrime = 0;
            break;
          }
        }
      }

      if (isPrime) {
        printf("%d is a prime number.\n", num);
      } else {
        printf("%d is not a prime number.\n", num);
      }

      return 0;
    }
  </code></pre>

  <p>This program takes an integer as input, checks its primality, and prints the result. You can enhance this further to find all primes within a range or improve efficiency for larger numbers.</p>

  <h3>Further Exploration</h3>
  <p>For a deeper dive into primality testing and optimizations, explore resources on number theory in C (link to be added later).</p>

</body>
</html>
-1
投票
#include<stdio.h>

int primeornot(int a)
{
    int i, number_to_increment=0;

    for(i=1;i<=a;i++)
    {
        if(a % i == 0)
        {
            number_to_increment+=1;
        }
        else
        {
            number_to_increment+=0;
        }
    }
    if(number_to_increment==2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

main()
{
    int number_given_by_user;

    printf("Enter a positive integer to find whether it is prime or not : ");
    scanf("%d",&number_given_by_user);

    if(primeornot(number_given_by_user))
    {
        printf("The given number is a prime number");
    }
    else
    {
        printf("The given number is not a prime number");
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.