Sapphire


私信TA

用户名:1368205885

访问量:4008

签 名:

无限进步!

等  级
排  名 700
经  验 3749
参赛次数 0
文章发表 16
年  龄 18
在职情况 学生
学  校
专  业 软件工程

  自我简介:

哥德巴赫猜想

Sapphire

2022/2/18

解题思路:
输入一个大于6的偶数n,要计算这个偶数n可以被分解为多少种俩素数之和,那么我们先写一个可以判断是素数与否的函数,遍历i(从3到n/2,为什么是这个?注意事项里会解释)只要判断i和n-i都为素数即可。


注意事项:
1.为什么遍历i从3开始,不从最小的素数2开始?

想一想,一个大于6的偶数可不可能分解成为2+能一个素数?我们知道,偶数可以等于奇数+奇数,也可以等于偶数+偶数,但是2是素数中唯一的偶数,所以绝不可能分解为2+另一素数。

2.从3开始遍历相对有什么好处?

减少了所占用空间内存和工作量以及运行时间。

如果从2开始遍历,for(i=2;i<=n/2;i++),若从3开始遍历,for(i=3;i<=n/2;i+=2),我们可以很明显的看到,从3开始遍历的工作量更小,因为其他偶数绝不可能为奇数,所以直接+=2。

3.为什么i的最大值是n/2?

因为如果遍历到最大值n的话,期间可能出现重复的情况,比如:10=3+7也等于7+3,而题目不允许这样的情况发生,为什么可以取等n/2?是为了不排除10=5+5,这个数刚好除以2得到一个素数的情况。


参考代码:

#include<stdio.h>
#include<math.h>
int isprime(int n)
{
    int i;
    for(i=2;i<=(int)sqrt(n);i++)
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n;
    int i;
    int count=0;
    printf("请输入一个大于6的偶数:>");
    scanf("%d",&n);
    if(n>6&&(n%2==0))
    {
        for(i=3;i<=n/2;i+=2)//因为10=5+5,后面再分解的话就重复了,所以i最大为n/2 
        {
            if(isprime(i)&&isprime(n-i))//n可以分解为两个素数,则i为素数,n-i也为素数 
            {
                printf("%d=%d+%d\n",n,i,n-i);
                count++;
            }
        }
    }
    printf("一共可以分解为 %d 种素数之和",count);
    return 0;
}

参考代码可以用来运行,请不要直接填入答案,否则是错误的哟。

如果文章有帮助到你,请评一个高分吧~

 

0.0分

2 人评分

  评论区

牛批,大佬
2022-03-28 00:01:12
  • «
  • 1
  • »