C程序求一个素数

Question

我写了一个 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");
    }
}

Answer 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!!
}

Answer 2

如果它不可整除，您将返回，因此迭代只会在 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");
    }
}

Answer 3

#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");
    }
}

Answer 4

函数 primeornot returns 在第一次测试后立即执行。您不会按预期测试每个除数 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) 并且你应该在消息和 return 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;
}

C程序求一个素数

C program to find a prime number

c

primes

for-loop

function