1528: [函数][判素][高级]陈氏定理

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:24 Solved:0

Description

t同学最近学习了陈氏定理,这个定理是我国著名数学家陈景润在证明哥德巴赫猜想的过程中发现的,定理的内容是:每个充分大的偶数都能表示成一个质数加上两个质数 的乘积。现在,小t同学要你编个程序验证,对于比较小的范围内的偶数这个定理是否仍然成立。以下给出两组验证:
  6=2+2*2
  8=2+2*3


Input

输入数据仅有一行,包含一个正偶数N(N≥6)

Output

 输出数据仅有一行,包含一个形如"N=A+B*C"的等式,要求ABC均为质数且B≤C。若有多组解,请输出B*C最小时的解 。

Sample Input Copy

1073741826

Sample Output Copy

1073741826=1073741741+5*17

HINT

 输入数据保证在长整型数longint的范围内,且数据保证有解。

编一个质数判断的函数会大大提高你的程序的效率。素数又称质数,指在一个大于1自然数中,除了1和此整数自身外,不能被其他自然数整除的数。如5是素数,因为5只能被1和自身整除6不是素数,因为6能被23整除。由于个数的约数都是成对出现的,我们在验证素数是可以充分利用这一点以提高程序运行的效率,以下代码仅供参考:

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.

如果in的约数,那么它的另一半就是n div i,例如324的约数,3的另一半就是8,我们只要穷举3就可以了,不需要再去穷举8,即如果i>n div i就不要再做下去了。

Source/Category