首页 > 代码库 > URAL 1356. Something Easier（哥德巴赫猜想）
URAL 1356. Something Easier（哥德巴赫猜想）
题目链接
题意 ： 给你一个数n，让你找出几个素数，使其相加为n，输出这些素数。
思路 ：
哥德巴赫猜想 ：
任何一个大于 6的偶数都可以表示成两个素数之和。
任何一个大于9的奇数都可以表示成三个素数之和。
而在该题中，偶数中2本身就是个素数，奇数中小于9的都是素数，所以只要写一个判断素数的函数即可，这样不在范围内的数就可以直接判断输出了。
任何一个整数N（N>=2)最多由三个素数相加构成。要分情况考虑：
1. 如果N为偶数，1）如果N==2，直接输出；
2）如果N>2，那么N一定可以写成两个素数的和；
2.如果N为奇数，1）如果N自身就是素数，则直接输出；
2）如果N由两个素数构成，这两个素数只可能是：2 和 N-2；
3）N为三个素数之和。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 5 using namespace std ; 6 7 bool prime(int n) 8 { 9 for(int i = 2 ; i * i <= n ; i++)10 {11 if(n % i == 0) return false ;12 }13 return true ;14 }15 int main()16 {17 int T,n ;18 scanf("%d",&T) ;19 while(T--)20 {21 scanf("%d",&n) ;22 if(n % 2 == 0)23 {24 if(n == 2)25 printf("2\n") ;26 // else if(n == 4) printf("2 2\n") ;27 else{28 for(int i = 3 ; i <= n ; i += 2)29 {30 if(prime(i) && prime(n-i))31 {32 printf("%d %d\n",i,n-i) ;33 break ;34 }35 }36 }37 }38 else39 {40 if(prime(n)) printf("%d\n",n) ;41 else if(prime(n-2)) printf("2 %d\n",n-2) ;42 //else if(prime(n-4)) printf("2 2 %d\n",n-4) ;43 else44 {45 bool flag = false ;46 for(int i = 3 ; i <= n ; i += 2)47 {48 for(int j = 3 ; j <= n ; j += 2)49 {50 if(prime(i) && prime(j) && prime(n-i-j))51 {52 printf("%d %d %d\n",i,j,n-i-j);53 flag = true ;54 break;55 }56 }57 if(flag) break ;58 }59 }60 }61 }62 return 0 ;63 }
URAL 1356. Something Easier（哥德巴赫猜想）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。