2012-07-13 08:24:27Morris
[UVA][sieve, bitmask] 10948 - The primary problem
Problem F: The primary problem.
Larry now lost most of his knowledge after spending a few years on deserted islands all over the place. When Ryan brought
up the fact that every even number greater than 3 can represented as the sum of two prime numbers, he couldn't believe it!
So now Larry is trying to come up with some kind of counterexample, and you can help him!
Input
Each line will contain an integer N greater than 3. The input will terminate when N is 0. N will not be bigger than 1 million.Output
For each test case, output one way of summing two prime numbers. If there are more than one set of sums for which this is true, choose the set of sum the maximizes the difference between them. See the sample output. If a number cannot be represented as the sum of two prime number, print "NO WAY!" as below:Sample Input
4 5 6 7 9 10 11 0
Sample Output
4: 2+2 5: 2+3 6: 3+3 7: 2+5 9: 2+7 10: 3+7 11: NO WAY!Note:
10 can be 3+7 or 5+5, and since 7-3 is bigger than 5-5, we choose 3+7.
#include <stdio.h>
#define maxL (1000000>>5)+1
int p[80000], pt = 0;
int mark[maxL];
int GET(int x) {
return mark[x>>5]>>(x&31)&1;
}
void SET(int x) {
mark[x>>5] |= 1<<(x&31);
}
void sieve() {
int i, j, k;
int n = 1000000;
for(i = 2; i <= n; i++) {
if(!GET(i)) {
for(k = n/i, j = i*k; k >= i; k--, j -= i)
SET(j);
p[pt++] = i;
}
}
}
int main() {
sieve();
int n, i;
while(scanf("%d", &n) == 1 && n) {
printf("%d:\n", n);
int hn = n/2, flag = 0;
for(i = 0; i < pt; i++) {
if(p[i] > hn)
break;
if(!GET(n-p[i])) {
printf("%d+%d\n", p[i], n-p[i]);
flag = 1;
break;
}
}
if(!flag)
puts("NO WAY!");
}
return 0;
}