检查一个数是否可以表示为两个质数之和的程序

Question

我编写了以下程序来检查给定数字是否可以表示为两个素数之和。它编译得很好，但没有按预期工作。例如，对于input = 16，它显示16 不能表示为两个质数之和。同样对于输入 = 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

这是更正后的代码：

/* 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 类型。

Answer 2

您的代码中有两个错误：

在您的函数 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 3

请注意，其他人已经发现了您的错误，但由于您要求优化版本，这里是一个运行速度会更快的版本。

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) 使用所谓的 "short circuit evaluation"。这意味着如果 prime(b) returns 0，prime(a - b) 将 而不是 是 called/evaluated 因为 0 && whatever 可以从不非零

Answer 4

你可以参考这个简单的代码

#include <stdio.h>
int check_Prime(int s)
{
    int flag = 0;
    for (int k = 2; k < s; k++)
    {
        if (s % k == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        return 1;
    else
        return 0;
}
int main()
{
    int n, i, j;
    printf("Enter the number : ");
    scanf("%d", &n);
    for (i = 1, j = n - 1; i < n / 2, j >= n / 2; i++, j--) {
        int a = check_Prime(i);
        int b = check_Prime(j);
        if (a == 1 && b == 1) {
            printf("%d = %d + %d\n", n, i, j);
        }
    }
}

考虑如果输入是34，变量i取值从1到34/2=17，j取值从34-1=33到17。

所以对应的和i+j就变成了

1+33，i加1，j减1

2+32

3+31......

现在通过函数check_Prime检查对应的i和j是否为素数，如果是则显示

检查一个数是否可​​以表示为两个质数之和的程序

Program to check whether a number can be expressed as a sum of two prime numbers

c

primes

完整代码

检查一个数是否可以表示为两个质数之和的程序