要用到一个基本的均值不等式：(a+b)^2>=4*a*b 很好证明，把4ab移到左侧，完全平方打开，然后合并。等号在a=b时成立。所以可以知道，和一定的两个数，越接近乘积越大。所以从S/2开始向两端枚举即可。O(n*sqrt(n))
当然还有一种简单的方法先用筛法筛出数据范围内的素数，枚举时直接判断即可O(n)
#include<iostream> #include<cstdio> using namespace std; int n; inline int pd(int x) { for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; } int main() { scanf("%d",&n); for(int i=n/2;i>=2;i--) if(pd(i)&&pd(n-i)){ printf("%d",i*(n-i)); return 0; } }
原文：http://www.cnblogs.com/xtx1999/p/4913067.html