Euler proved in one of his classic theorems that prime numbers are infinite in number. But can every number be expressed as a summation of four positive primes? I don’t know the answer. May be you can help!!! I want your solution to be very efficient as I have a 386 machine at home. But the time limit specified above is for a Pentium III 800 machine. The definition of prime number for this problem is “A prime number is a positive number which has exactly two distinct integer factors”. As for example 37 is prime as it has exactly two distinct integer factors 37 and 1.
Input
The input contains one integer number N (N ≤ 10000000) in every line. This is the number you will have to express as a summation of four primes. Input is terminated by end of file.
Output
For each line of input there is one line of output, which contains four prime numbers according to the given condition. If the number cannot be expressed as a summation of four prime numbers print the line ‘Impossible.’ in a single line. There can be multiple solutions. Any good solution will be accepted.
Sample Input
24 36 46
Sample Output
3 11 3 7 3 7 13 13 11 11 17 7
题目类型：扩展哥德巴赫猜想
算法分析：要找到4个满足条件的素数，可以考虑先将前两个素数找到，其中如果n为奇数，则将其减去奇数(2 + 3)；如果是偶数，则将其减去偶数(2 + 2)。然后再按照哥德巴赫猜想来判断n是否能够构成两个奇素数。这里构造的素数表一定要使用线性筛(Euler筛)，否则会TLE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 10000000 + 66; bool prime[maxn]; int primelist[maxn], num; void PrePare () { memset (prime, true, sizeof (prime)); num = 0; int i; for (i = 2; i <= maxn; i++) { if (prime[i]) primelist[num++] = i; int j; for (j = 0; j < num; j++) { if (i * primelist[j] > maxn) break; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } } int main() { // ifstream cin ("aaa.txt"); PrePare (); int n; while (cin >> n) { if (n < 8) cout << "Impossible." << endl; else { if (n % 2) { n -= 5; cout << "2 3"; } else { n -= 4; cout << "2 2"; } bool is_find = false; int i; for (i = 0; i < num; i++) { if (n <= primelist[i]) break; if (prime[n-primelist[i]]) { is_find = true; break; } } if (is_find) cout << " " << primelist[i] << " " << n - primelist[i] << endl; else cout << "Impossible." << endl; } } return 0; } |
- « 上一篇：uva1600
- uva10533：下一篇 »