厦大C语言上机 1393 哥德巴赫猜想的验证
1393.哥德巴赫猜想的验证时间限制: 1000 MS 内存限制: 65536 K
提交数: 591 (0 users) 通过数: 245 (238 users)
问题描述
著名的哥德巴赫猜想是这样的。1.“任何一个大于二的偶数都可以分解成两个素数之和”。2.“任何一个大于5的奇数都可以分解成三个素数之和”。现在请你写两个函数验证一下这个著名的猜想。
输入格式
输入只有一个整数N，代表要验证的数，5<=N<=10000，当N为偶数时，用验证哥德巴赫猜想1，当N为奇数时，验证哥德巴赫猜想2。
输出格式
对于输入的N，输出相应的表达式，要求加数构成的序列的字典序最小，即确保第一位最小，再确保第二位最小（再确保第三位最小）。
例如N=13，13=3+3+7=7+3+3。
则应输出
13=3+3+7
样例输入
8
样例输出
8=3+5
来源
xmu
#include <stdio.h>
int is_prime(int n)
{
int i;
if (n == 1)
return 0;
for (i = 2; i*i <= n; ++i)
{
if (n % i == 0)
return 0;
}
return 1;
}
int main()
{
int n;
int i, j;
scanf("%d", &n);
printf("%d=", n);
if (n % 2 == 0)
{
for (i = 2; i*2 <= n; ++i)
{
if (is_prime(i) && is_prime(n-i))
{
printf("%d+%d\n", i, n-i);
break;
}
}
}
else
{
for (i = 2; i*3 <= n; ++i)
{
for (j = 2; j*2 <= n-i; ++j)
{
if (is_prime(i) && is_prime(j) && is_prime((n-i-j)))
{
printf("%d+%d+%d\n", i, j, n-i-j);
return 0;
}
}
}
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/liulizhi1996/3032796
页:
[1]