| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3170 人关注过本帖
标题:[讨论]第十二期编程题目(尽情发挥)
只看楼主 加入收藏
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 

也给你顶一下第三个.
那个公式不错


2007-04-22 10:36
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 

第二个实在没法优化了,以后再想想,勉强可以达到题目的要求,1000000以内的数可以在1秒之内算出

#include<stdio.h>
#include<math.h>
#include<time.h>

int a[168]={2};

void init(void) //求出1000以内的所有素数,储存在数组中
{
int i,j,k=1,sure=1;
for(j=3;j<1000;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
/* for(i=0;i<168;i++) //输出1000以内的素数
printf("%5d",a[i]);
*/
}

int prime(long n) //判断该数是否为素数
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=0;i<168;i++)
{
if(a[i]>sqrt(n))
break;
if(n%a[i]==0)
return 0;
}
return 1;
}

int main(void)
{
long m,n,i;
clock_t start,over; // 定义两个变量用来储存时间
int sum;

while(scanf("%ld%ld",&m,&n))
{
start=clock(); //记录起始时间
init();
sum=1;
if(m%2==0)
{
if(prime(m))
sum++;
i=m+1;
}
else
i=m;
for(;i<=n;i+=2)
if(prime(i))
sum++;
printf("%d\n",sum);
over=clock(); //记录结束时间
printf("消耗时间:%lfms\n",(double)(over-start)); //输出程序运行时间
}
return 0;
}

[此贴子已经被作者于2007-4-22 11:22:45编辑过]


雁无留踪之意,水无取影之心
2007-04-22 11:20
asdf12347066
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-4-26
收藏
得分:0 
第一题
/*歌德巴赫猜想*/
# include<stdio.h>
# include<math.h>
int fun(int m)
{
int i,n,flag=1;
n=sqrt(m);
if(m==1 || m==3)
flag=1;
else if(m==2)
flag=0;
else
for(i=2;(i<=n && flag==1);i++)
if(m%i==0)
flag=0;
return(flag);
}
void main()
{
int m,i,flag,x;
printf("enter n:");
scanf("%d",&m);
printf("%d=",m);
for(i=1;i<=m/2;i++)
{
flag=fun(i);
if(flag)
{
x=m-i;
if((flag=fun(x))==1)
printf("%d+%d=",i,x);
}
}
printf("\n");
}

2007-04-26 21:29
asdf12347066
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-4-26
收藏
得分:0 
第二题
# include<stdio.h>
# include<math.h>
int fun(int m)
{
int i,n,flag;
n=sqrt(m);
for(i=2;i<=n;i++)
{
if(m%i==0)
break;
}
if(i==n)
flag=1;
else
flag=0;
return(flag);
}
void main()
{
int m,n,i,flag,temp,x=0;
printf("please input m && n:");
scanf("%d%d",&m,&n);
if(m>n)
{
temp=m;m=n;n=temp;
}
for(i=m;i<=n;i++)
{
flag=fun(i);
if(flag)
x++;
}
printf("have %d data.\n",x);
}

2007-04-26 21:32
asdf12347066
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-4-26
收藏
得分:0 
不好意思,刚发的第二题错了,我改了下
# include<stdio.h>
# include<math.h>
int fun(int m)
{
int i,n,flag;
n=sqrt(m);
if(m==1 || m==3)
flag=1;
else(m==2)
flag=0;
else
{
for(i=2;i<=n;i++)
{
if(m%i==0)
break;
}
if((i-1)==n)
flag=1;
else
flag=0;
}
return(flag);
}
void main()
{
int m,n,i,flag,temp,x=0;
printf("please input m && n:");
scanf("%d%d",&m,&n);
if(m>n)
{
temp=m;m=n;n=temp;
}
for(i=m;i<=n;i++)
{
flag=fun(i);
if(flag)
x++;
}
printf("have %d data.\n",x);
}

2007-04-26 21:48
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
# include<stdio.h>
# include<math.h>
int fun(int m)
{
int i,n,flag;
n=sqrt(m);
if(m==1 || m==3)
flag=1;
else(m==2) //是不是有点问题
flag=0;
else
{
for(i=2;i<=n;i++)
{
if(m%i==0)
break;
}
if((i-1)==n)
flag=1;
else
flag=0;
}
return(flag);
}
void main()
{
int m,n,i,flag,temp,x=0;
printf("please input m && n:");
scanf("%d%d",&m,&n);
if(m>n)
{
temp=m;m=n;n=temp;
}
for(i=m;i<=n;i++)
{
flag=fun(i);
if(flag)
x++;
}
printf("have %d data.\n",x);
}

[此贴子已经被作者于2007-9-2 21:08:04编辑过]


雁无留踪之意,水无取影之心
2007-04-26 22:04
evil_evil
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2006-3-4
收藏
得分:0 
NO 2

首先用一断小程序求出所有的素数,再统计个数
统计1--4194304的素数大概200多MS,
当然,只处理奇数时间可以省半

[CODE]
#include < iostream >
#include < vector >
#include < cmath >
using namespace std;

#define N 1000000

int main(int argc, char *argv[])
{
int a,b,i,j,k;
vector<int>t(N,1);
t[0]=t[1]=0;
for(i=2;i<sqrt(double(N));i++)
if(t[i])
for(j=i;j*i<N;j++)t[j*i]=0;

while(cin>>a>>b)
{
k=0;
for(int i=a;i<=b;i++)
if(t[i])k++;
cout<< k << endl;
}
}
[/CODE]

[此贴子已经被作者于2007-4-26 22:16:10编辑过]


潜水员!
2007-04-26 22:06
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 

第二个
应该先把2-1000000中间的素数全部保存起来.(当然是先写个程序,把这些值算出来,再放到一个数组里).
然后就是对每个数一次遍历就可以了,效率应该很快.


倚天照海花无数,流水高山心自知。
2007-04-26 22:25
evil_evil
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2006-3-4
收藏
得分:0 
NO 1
跟 NO 2差不多
[CODE]
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define N 1000000
int main(int argc, char *argv[])
{
int a,i,j,k,f;
vector<int>t(N,1);
t[0]=t[1]=0;
for(i=2;i<sqrt(double(N));i++)
if(t[i])
for(j=i;j*i<N;j++)t[j*i]=0;

while(cin>>a&&a)
{
f=1;
for(k=0;k<N/2;k++)
if(a-k>1&&t[k]&&t[a-k]){
f=0;
cout<<a<<" = "<<k<<" + "<<a-k<<endl;
break;
}
if(f)
cout<<"Goldbach's conjecture is wrong." <<endl;
}
}[/CODE]

潜水员!
2007-04-26 22:33
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
以下是引用nuciewth在2007-4-26 22:25:11的发言:

第二个
应该先把2-1000000中间的素数全部保存起来.(当然是先写个程序,把这些值算出来,再放到一个数组里).
然后就是对每个数一次遍历就可以了,效率应该很快.

没必要存那么多吧,只要存1000以内的就可以了,因为只要考虑小于或等于sqrt(n)的就可以了


雁无留踪之意,水无取影之心
2007-04-27 10:32
快速回复:[讨论]第十二期编程题目(尽情发挥)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.045400 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved