Программа для проверки, может ли число быть выражено как сумма двух простых чисел

Question

Я написал следующую программу, чтобы проверить, можно ли выразить данное число в виде суммы двух простых чисел. Компилируется нормально, но не работает как положено. Например, для input = 16 это показывает, что 16 не может быть выражено как сумма двух простых чисел. Также, например, для input = 5 отображается 5 = 3 + 2, а не 5 = 2 + 3.

/* Program to check whether a number can be expressed as a sum of two prime numbers*/
#include <stdio.h>
#include <stdlib.h>

int prime(int x)
{
    int fact=0,i;
    for(i=2;i<x;i++)
    {
        if(x%i==0)
        {
            fact++;
            break;
        }
    }
    if (fact==0)
        return 1;
    else return 0;
}
int main()
{
    int a,b,c,d,count=0;
    printf("Enter Number\n");
    scanf("%d",&a);
    for(b=2;b<(a+1)/2;b++);
    {
        c = prime(b);
        d = prime(a-b);
        if (c==1 && d==1)
        {
            printf("%d = %d + %d\n",a,b,a-b);
            count++;
        }
    }
    if(count==0)
        {
            printf("%d cannot be expressed as sum of two prime numbers.\n",a);
        }
    return 0;
}

Answer 1

В вашем коде есть две ошибки:

В вашей функции prime() вы не проверяете x на значение 2, которое также будет простым числом.

Вторая ошибка - ; после оператора for.

for(b=2;b<(a+1)/2;b++);

Удалите его, в противном случае следующий блок (часть между { и }) выполняется не для каждой итерации цикла, а только после его окончания.

Обычно вы не хотите читать число с плавающей точкой, вам нужно целое число. Используйте fgets() и atoi() для вашего случая использования. Это намного безопаснее, чем scanf().

В качестве последнего пункта: добавьте пробелы до и после операторов. Это делает код намного более читабельным.

полный код

#include <stdio.h>
#include <stdlib.h>

int prime(int x)
{
    int i;

    if (x == 2)
    {
        return 1;
    }

    for (i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            return 0;
        }
    }

    return 1;
}

int main()
{
    int read_number;
    int summand1;
    int summand2;
    int count = 0;
    int max;
    char buffer[100];

    printf("Enter Number\n");
    fgets(buffer, sizeof(buffer), stdin);
    read_number = atoi(buffer);

    max = (read_number + 1) / 2;

    for (summand1 = 2; summand1 < max; ++summand1)
    {
        summand2 = read_number - summand1;
        if ((prime(summand1) == 1) && (prime(summand2) == 1))
        {
            printf("%d = %d + %d\n", read_number, summand1, summand2);
            count++;
        }
    }

    if (count == 0)
    {
        printf("%d cannot be expressed as sum of two prime numbers.\n", read_number);
    }

    return 0;
}

Конечно, вы могли бы сделать некоторые оптимизации. Например, в prime(): если вы уже проверили, что x не кратно 2, вы можете начать цикл с 3 и увеличить i на 2 в самой итерации. Или вы можете остановить этот цикл, если i больше квадратного корня из x. Эти меры могут ускорить ваш код для больших чисел, но это может сделать код менее читабельным. Об этом нужно помнить, особенно если вы начинаете изучать программирование.

Answer 2

Обратите внимание, что другие заметили ваши ошибки, но поскольку вы запросили оптимизированную версию, вот версия, которая будет работать немного быстрее.

Функция prime переходит только к sqrt(x) и просматривает только нечетные значения в основном цикле. Кроме того, в main цикл просматривает только нечетные значения.

/* Program to check whether a number can be expressed as a sum of two prime
numbers*/
#include <stdio.h>
#include <stdlib.h>

int
prime(int x)
{
    int pflg = 1;
    int sqr;
    int i;

    // 2,3 are prime
    if (x <= 3)
        return (x >= 2);

    // even numbers are not
    if ((x & 1) == 0)
        return 0;

    // get sqrt(x)
    for (sqr = 0;  (sqr * sqr) < x;  ++sqr);

    // we only need to check odd numbers
    for (i = 3; i <= sqr; i += 2) {
        if (x % i == 0) {
            pflg = 0;
            break;
        }
    }

    return pflg;
}

int
main()
{
    int a,
     b,
     a2,
     count = 0;

    printf("Enter Number\n");
    scanf("%d", &a);

    a2 = (a + 1) / 2;

    // check when b is 2
    b = 2;
    if (b < a2) {
        // NOTE: if prime(b) is 0, no need to calculate prime(a - b)
        if (prime(b) && prime(a - b)) {
            printf("%d = %d + %d\n", a, b, a - b);
            count++;
        }
    }

    // only odd b values can be prime
    for (b = 3; b < a2; b += 2) {
        // NOTE: if prime(b) is 0, no need to calculate prime(a - b)
        if (! prime(b))
            continue;
        if (! prime(a - b))
            continue;
        printf("%d = %d + %d\n", a, b, a - b);
        count++;
    }

    if (count == 0) {
        printf("%d cannot be expressed as sum of two prime numbers.\n", a);
    }

    return 0;
}

Обратите внимание, что в main if (prime(b) && prime(a - b) использует то, что называется "оценкой короткого замыкания". Это означает, что если prime(b) вернет 0, prime(a - b) будет не вызван / оценен, потому что 0 && whatever может никогда быть ненулевым

Answer 3

Вот исправленный код:

/* Program to check whether a number can be expressed as a sum of two prime numbers*/
#include <stdio.h>
#include <stdlib.h>

int prime(int x)
{
    int fact=0,i;
    if(x < 2) return 0;
    for(i=2;i<x;i++)
    {
        if(x%i==0)
        {
            fact++;
        }
    }
    if (fact==0)
        return 1;
    else return 0;
}
int main()
{
    int a;
    int b,c,d,count=0;
    printf("Enter Number\n");
    scanf("%d",&a);
    for(b=2;b<(a+1)/2;b++)//;mistake here!!
    {
        c = prime(b);
        d = prime(a-b);
        if (c==1 && d==1)
        {
            printf("%d = %d + %d\n",a,b,a-b);
            count++;
        }
    }
    if(count==0)
        {
            printf("%d cannot be expressed as sum of two prime numbers.\n",a);
        }
    return 0;
}

Основная проблема заключалась в том, что вы заканчивали цикл с полуколонкой ;. Другое предложение - везде использовать int.