题目
| 简单的素数问题 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
|
试题描述
|
|
已知三个素数的和为 n ，正整数 n 由键盘输入，计算并输出这三个素数乘积的最大值。
|
|
输入
|
|
一个正整数 n（给定的测试数据中 n 一定是偶数）。
|
|
输出
|
|
一个数，表示三个素数乘积的最大值
|
|
输入示例
|
|
42
|
|
输出示例
|
|
782
|
|
其他说明
|
|
数据范围： 10 <= n <= 10000 。
|
分析
这道题我们需要知道一些方法和常识。
首先，题目中说“给定的测试数据中n一定是偶数”。我们都知道除2之外其他质数都是奇数。而此题有三个质数，和必为奇数。由此推出这三个指数中必有一个偶数，即唯一的偶质数2。
其次，要想判断一个数是否为质数，我们需要用两重循环。外层循环来找出你需要判断的数。内层循环从2开始，到该数的开方（好像数学上就是这么做的）或该数减一结束（一定不能到该数在结束，不然任何数都是合数了）。如果外层循环找出的数除以内层循环当前的数余数为0，及该数为合数，可以停止判断如果内层循环自增到和外层循环找出的数一样，即该数为质数。或者提前立一个初始值赋0的flag，在外层循环找出的数除以内层循环当前的数余0时，flag赋1。循环结束后判断一下flag的值也行。
说了这么多，到底该怎么用呢？
代码
#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,a,b,c;
int main()
{
scanf("%d",&n);
n-=2;//题目中说“给定的测试数据中n一定是偶数”，三个奇数之和必为奇数，所以必有2。
for(i=n/2;i<=n;i++)//和一定差小积大。
{
for(j=2;j<i;j++) if(!(i%j)) break;//i被j整除说明i是合数。
if(j==i)//j自增到i说明i为质数。
{
for(k=2;k<n-i;k++) if(!((n-i)%k)) break;//(n-i)被k整除说明(n-i)是合数。
if(k==n-i)//k自增到(n-i)说明(n-i)为质数。
{
printf("%d",i*(n-i)*2);//输出刚找到两数和2的积。
break;//马上退出。
}
}
}
return 0;
}