pascal编程:哥德巴赫猜想(升级版)

发布网友发布时间：2022-05-26 00:22

共1个回答

热心网友时间：2024-10-21 06:53

由于“n大于9并且小于10000”，用朴素算法应该也不会超时。

这里提供一种优化的算法：

先构造2~10000以内的质数表，并除去其中的2，就能得到3~10000以内的奇质数表；

令 i 从 3开始循环（这是外循环），j 从3开始循环（这是内循环），然后判断（n-i-j）是不是质数，如果是，就 writeln(i,' ',j,' 'n-i-j).

完整代码如下：
program Goldbach;
var prime:array[2..10000]of boolean;
      i,j,n:longint;
begin
  readln(n);
  for i:=2 to trunc(sqrt(n)) do
   if not prime[i] then
   begin
    for j:=2 to n div i do
     prime[i*j]:=true;
  end;

  for i:=3 to n do
   if not prime[i] then
    for j:=3 to n do
     if not prime[j] then
      if not prime[n-i-j] then
      begin
        writeln(i,' ',j,' ',n-i-j);
        exit;
      end;
end.

真的不长吧？最大的数9999也不用1秒。
筛法求素数是一个很常用的算法，请LZ一定要掌握。
祝学习进步。

我不会这个语言，所以帮你百度上找到的，如果c语言，还行

http://zhidao.baidu.com/question/553416068.html 来源