首页 > 代码库 > ural 1356. Something Easier 哥德巴赫猜想
ural 1356. Something Easier 哥德巴赫猜想
1356. Something Easier
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
“How do physicists define prime numbers? Very easily: prime numbers are the number 2 and all the odd numbers greater than 2. They may show that this definition corresponds to the mathematical one: 3 is prime, 5 is prime, 7 is prime… 9? 9 is certainly not prime. Then: 11 is prime, 13 is prime. So 9 is the experiment mistake.”
From mathematical analysis course
Once physicist and mathematician argued how many prime numbers one needed for the purpose that their sum was equal to N. One said that it wasn’t known and the other that 3 was always enough. The question is how many.
Input
The first line contains T, an amount of tests. Then T lines with integer N follow (0 ≤ T ≤ 20; 2 ≤ N ≤ 109).
Output
For each test in a separate line you should output prime numbers so that their sum equals to N. An amount of such prime numbers is to be minimal possible.
Sample
| input | output |
|---|---|
7227851921498337 | 223 2 22 8311 1811498337 |
Problem Author: Aleksandr Bikbaev
Problem Source: USU Junior Championship March‘2005
思路：（1） 当n为偶数的时候， n > 4 n可以分解成两个素数的和
（2）当n为奇数的时候， 如果n是素数就直接输出；
如果n-2也是素数， 可以直接输出 2 n-2；
那么把奇数n分解为三个奇素数；
很好奇这么高的复杂度，竟然跑的这么快啊
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 bool fun(int x){ 6 if(x <= 1) return false; 7 for(int i = 2; i*i <= x; i++){ 8 if(x%i == 0){ 9 return false;10 }11 }12 return true;13 }14 15 int main() {16 //freopen("in.txt", "r", stdin);17 int t, n;18 scanf("%d", &t);19 while(t--) {20 scanf("%d", &n);21 if(n%2 == 0){22 if(n == 2){23 puts("2");24 }else if(n == 4){25 puts("2 2");26 }else {27 for(int i = 3; i < n; i += 2){28 if(fun(i) && fun(n-i)){29 printf("%d %d\n", i, n-i);30 break;31 }32 }33 }34 }else {35 if(fun(n)) printf("%d\n", n);36 else {37 if(fun(n-2)){38 printf("2 %d\n", n-2);39 }else {40 int flag = 1;41 for(int i = 3; i < n; i += 2){42 for(int j = 3; j < n - i; j += 2){43 if(fun(i) && fun(j) && fun(n-i-j)){44 if(flag) {45 printf("%d %d %d\n", i, j, n-i-j);46 flag = 0;47 break;48 }49 }50 }51 if(!flag) break;52 }53 }54 }55 }56 }57 return 0;58 }
ural 1356. Something Easier 哥德巴赫猜想
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。