题目链接
http://bailian.openjudge.cn/practice/4138/
素数的Esieve筛选法
截图自百度百科
那这道题就可以从 s/2 的位置向前向后查找素数表,找到第一对素数就是最大的素数积。
cpp代码
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAX 10010
int prime[MAX];
void pick(int n){
memset(prime, -1, sizeof(prime));
prime[1] = 0;
for(int i = 2; i*i <= n; i++)
if(prime[i])
for(int j = i + i; j <= n; j+= i)
prime[j] = 0;
}
int main(){
int s;
pick(MAX);
scanf("%d", &s);
if(s % 2){
if(prime[s-2])
printf("%d\n", 2 * (s - 2));
}
else{
int i, j;
for(i = j = s/2; !prime[i] || !prime[j]; i--, j++);
printf("%d\n", i * j);
}
return 0;
}