由于“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 来源
#includevoid main( )
{
int i, j, k, IsPrime
for(i = 4i <= 100i += 2) /*偶数i从4到100*/
{
for(j = 2j <= i / 2j++) /* 将j从2到i/2进行测试 */
{
for(k = 2, IsPrime = 1(k <= j / 2) &&IsPrimek++) /*判断j是否为素数*/
if(j % k == 0) IsPrime = 0
if(IsPrime) { /*如果j是素数*/
for(k = 2, IsPrime = 1(k <= (i - j) / 2) &&IsPrimek++) /*判断i-j是否是素数*/
if((i - j) % k == 0) IsPrime = 0
if(IsPrime) /*如果i-j也是素数,则找到了i的一个解,将其输出,下一个偶数i*/
{
printf("%d = %d + %d\t", i, j, i - j)
break
}
}
}
}
}
除了printf与main外,没有用到其他任何的函数,楼主不妨试一试。
网上标准答案一)设计思想:
1:为了证明一个小于都2000的偶数,能被两个素数相加,首先求出1-2000内的所有素数,以方便相加,我们将保存在一个sushu[2000]数组中备用。
2:从键盘输入一个偶数后在核心函数中处理,寻找合适的两个素数。
3:输出结果。
二)流程图:
(画不出来改成文字了)
1:声明所需的变量及数组
2:求出所有2000以内的素数保存在数组中备用。
3:输入一个偶数,并在素数组中寻找合适的两个素数
4:将结果输出
三)难重点及解决方法:
1:2000以内的素数的求出,我们用了两个循环套来使得素数各方面条件都得到满足后保存入数组。
2:查找满足的两个素数,为了能查到匹配的两个素数,我们也用了两个循环套来保证一个不漏的找到。
四)核心内容:
1:求素数的内容如下:
s=ss=0
sushu[0]=2
xiabiao=1
for (int s=3s<2000s++)
{
for (int ss=2ss<=sss++)
{
if (0==s%ss) break
}
if (s==ss) sushu[xiabiao++]=s
}
////////////////////////////////////////////////////
2:查找匹配的两个素数的内容如下:
for (s=0s<xiabiao-1s++)
{
for (ss=s+1ss<xiabiaoss++)
{
if (m_1==sushu[s]+sushu[ss])
{
m_2=sushu[s]
m_3=sushu[ss]
UpdateData(FALSE)
return
}
}
}