小t同学最近学习了陈氏定理,这个定理是我国著名数学家陈景润在证明哥德巴赫猜想的过程中发现的,定理的内容是:每个充分大的偶数都能表示成一个质数加上两个质数 的乘积。现在,小t同学要你编个程序验证,对于比较小的范围内的偶数这个定理是否仍然成立。以下给出两组验证:
6=2+2*2
8=2+2*3
输入数据仅有一行,包含一个正偶数N(N≥6)。
输出数据仅有一行,包含一个形如"N=A+B*C"的等式,要求A、B、C均为质数且B≤C。若有多组解,请输出B*C最小时的解 。
1073741826
1073741826=1073741741+5*17
输入数据保证在长整型数longint的范围内,且数据保证有解。
编一个质数判断的函数会大大提高你的程序的效率。素数又称质数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。如5是素数,因为5只能被1和自身整除;6不是素数,因为6能被2或3整除。由于一个数的约数都是成对出现的,我们在验证素数是可以充分利用这一点以提高程序运行的效率,以下代码仅供参考:
var i,n:longint;
flag:boolean;
begin
read(n);
flag:=true;
for i:=2 to n do
begin
if i>n div i then break;
if n mod i=0 then flag:=false;
end;
writeln(flag);
end.
如果i是n的约数,那么它的另一半就是n div i,例如3是24的约数,3的另一半就是8,我们只要穷举3就可以了,不需要再去穷举8,即如果i>n div i就不要再做下去了。