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

Функция 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;
}

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

Не только кратные 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!!
}