C程序查找素数 [英] C program to find a prime number

问题描述

我写了一个C程序，它告诉给定的数字是否为质数.但这有一个问题.对于除5的倍数以外的数字，它可以正常工作，但它显示的5的倍数为质数，例如15，25，35，45 ....我找不到错误.我曾尝试将其与互联网上的其他程序进行比较，但找不到错误.

I wrote a C program which tells whether a given number is prime or not. But it has a problem in it. It is working fine for numbers other than multiples of 5. But it is showing the multiples of 5 as prime like 15, 25, 35, 45... . I am not able to find the error. I've tried comparing it with other programs on the internet but I am not able to find the error.

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

推荐答案

不仅5的倍数(例如，您的代码还将9视为素数)

Not only multiples of 5 (for example, 9 is also considered prime by your code)

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

Your code is flawed. You are using a loop but only checking the first iteration, since you have a return inside each branch of the condition inside your loop:

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)，这不是一个很好的素数查找算法:-)

In this form, your code only does return !(input % 2) which is not a very good prime finding algorithm :-)

您需要做的是检查所有迭代，并且只有当所有迭代都转到else分支时，数字才是素数.

What you need to do is check all the iteration, and only if all of them go to the else branch, the number is prime.

因此，更改为:

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

这篇关于C程序查找素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！