请教验证歌德巴赫猜想的算法优化问题

C语言 码拜 10年前 (2015-05-11) 998次浏览 0个评论
 

这是OJ平台上的一道题

题目如下:

验证歌德巴赫猜想

要求:Time Limit: 400/200 MS (Java/Others)     Memory Limit: 32768/5000 K (Java/Others)
请教验证歌德巴赫猜想的算法优化问题

我自己写了一份代码,用的是筛选法求素数,但提交后还是Time Limit Exceeded,是筛选法还不够优化还是我后面那个输出的方法不够好,或者我的代码中有哪些不足或不妥的地方,请各位大神不吝指出,谢谢

以下是本人的代码:

#include<stdio.h>

int main()
{
    int n,i,t,p,q,a[10001],k,w;

    while(scanf(“%d”,&n)==1)//用筛选法求出所有素数
    {
        t=1;
        a[1]=2;
        for(i=3; i<=n; i++)
        {
            if(i%2!=0)
            {
                t++;
                a[t]=i;
            }
        }

        for(p=1; p<t; p++)
        {
            if(a[p]!=0)
                for(q=p+1; q<=t; q++)
                {
                    if(a[q]%a[p]==0)
                        a[q]=0;
                }
        }

        k=0;

        if(t%2!=0)//将a[t]一分为二,前部分为较小数,后部分为较大数
            w=t/2+1;
        else
            w=t/2;

        for(p=w; p>=1; p–)//思路是”用较小数中的最大数”加上”较大数中的最小数”,不满足判断条件的话,较大数中的最小数再往后变大
        {
            if(a[p]!=0)
            {
                for(q=w; q<=t; q++)
                    if(a[q]!=0)
                    {
                        if(a[p]+a[q]==n)
                        {
                            printf(“%d %d\n”,a[p],a[q]);
                            k=1;
                            break;
                        }
                    }
            }

            if(k==1)
                break;
        }
    }

    return 0;
}

20分
这样可好:

char primes[10000];
int i, j, n;
int main(void)
{
	//先找出10000以内的所有素数
	memset(primes, ""1"", 10000);
	for (i = 2; i < 5000; i++)
		for (j = i*2; j < 10000; j+=i)
		primes[j] = ""0"";
	while (1 == scanf("%d", &n))
	{
		j = n / 2;
		while (""0"" == primes[j] || ""0"" == primes[n - j]) j--;
		printf("%d %d\n", j, n - j);
	}
	return 0;
}
20分
事先求好素数表,运算时直接查表,这才是最快的做法。
这个题目明显歧视Java啊
数据最多有多少组?
引用 1 楼 zhangxiangDavaid 的回复:

这样可好:

char primes[10000];
int i, j, n;
int main(void)
{
	//先找出10000以内的所有素数
	memset(primes, ""1"", 10000);
	for (i = 2; i < 5000; i++)
		for (j = i*2; j < 10000; j+=i)
		primes[j] = ""0"";
	while (1 == scanf("%d", &n))
	{
		j = n / 2;
		while (""0"" == primes[j] || ""0"" == primes[n - j]) j--;
		printf("%d %d\n", j, n - j);
	}
	return 0;
}

谢谢提醒

引用 2 楼 bravery36 的回复:

事先求好素数表,运算时直接查表,这才是最快的做法。

恩恩


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明请教验证歌德巴赫猜想的算法优化问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!