题目出的太..好了...
我都过不去..
我替EASTSUN讲解一下,要是让他讲估计几句话就搞定了
这个题目描述的那个素数的定义是骗人的.要是你真的去那么做肯定就超了时间了.
所以要用数论书上的那个E什么(是个E开头的英文单词,大家千万不要以为是"eastsun"这个单词啊
)的筛选法.
先来点理论知识:
比如让你找出1到10的素数
1 2 3 4 5 6 7 8 9 10
先把2的倍数去掉,2当然要留下了:
2 3 5 7 9
在把3的倍数给去掉:
2 3 5 7
答案就出来!
分析一下计算次数:设素数有p1,p2,,,,pi
计算次数分别应该是:n/p1,n/p2... 事实上他远小于这个数,具体时间复杂度我也说不上来.但是素数的增长是很快(几百个素数就能增加到好多万)的
先看一下我的那个漫游了4s的程序:
#define PB_ID 69
#include<stdio.h>
#define maxn 4000009
int flag[maxn]={0};//用来标志,如果flag[i]是0则表示他有可能是个素数
void init()
{
int i,j;
int cnt=0;//cnt表示的是从1到i出现的素数个数
for(i=2;i<maxn;i++)
{
if(flag[i]==0)//如果flag[i]是0表示的是在i之前的没有任何一个数是它的约数.也就是他是个素数
{
cnt++;
for(j=i+i;j<maxn;j+=i) flag[j]=1;//那么i的倍数肯定都不是素数了,
}
flag[i]=cnt;
}
}
int main()
{
int n,m,i,j;
init();
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n>m)
{
i=n;
n=m;
m=i;
}
printf("%d\n",flag[m]-flag[n-1]);
}
return 0;
}
结果还是超时间
再看一下eastsun的程序和我的比较一下:(他给我的时候有不知道他那程序是dev-c造还是txt造缩进怪怪的.我做了一下修改)
初一看大家都觉得比我上面那个高深好多,其实原理是一样的
#define PB_ID 69
#include<stdio.h>
#define MAX 4000000
#define SQL 2000
char flags[MAX/2 +2];//这个数组也是用来标记是不是素数的
int count[MAX+2];//刚开始的时候都是0,但在作完筛选之后是素数的元素都会变成1
int offset[] ={0,3,5,6,8,9,11,14};
int primes[] ={2,3,5,7,11,13,17,19,23,29};
int main()
{
int m,n,i,j,p;
for(i =0;i<10;i++) count[primes[i]] =1;//看见了没有,我上面没说错吧
p =3;
while(p<=SQL)
{
for(i =p*p/2;i<=MAX/2;i +=p) flags[i] =1;//好像很复杂吧?其实flag[i]标记的不是i而是2*i+1
//厉害的是他居然发现如果p是个素数i=(p*p/2)*2+1就是p的个倍数,注意那/是c语言里的整数除法.并且2*i+1也是
//一个合数,要发现这个还是有点难度
.虽然证明起来简单
//证明一下p因为是个奇数所以可以表示为2*k+1,i=(p*p/2)=2*k^2+2*k,2*i+1=(2k+1)^2,显然是个合数,
// (i+p)*2+1=4*k^2+8*k+3=(2*k+1)*(2*k+3).太假了这样都能被他发现,这个结论其实并不那么明显直接
do
{
p +=2;
}
while(flags[p>>1]);//因为p是被p/2 标记的,所以意思和我上面一样,
}
p =0;
for(i =15;p<=MAX/2;i+=15)
{
for(j=0;j<=7;j++)
{
p =i +offset[j];
if(p>MAX/2) break;
if(!flags[p]) count[(p<<1)|1] =1; //看见了没有,我上面没说错吧,是不是有的变1了
}
}
for(i=1;i<=MAX;i++) count[i] +=count[i-1];
while(scanf("%d%d",&m,&n)!=EOF)
{
if(m>n)
{
p =m;
m =n;
n =p;
}
printf("%d\n",count[n]-count[m-1]);
}
}
细心的人已经发现他快在哪里了!
还是比较一下:
很明显可以发现如果一个数能分解成k个不同素数的乘积,如果你不做任何处理的话你要筛选这个数字k次.
(4000000内的任何数字最多由10个不同素数组成.所以这个算法的时间下界是10n,事实远远比它好.)
我上面的程序很明显多做了很多没有必要的事情,比如i是偶数的话根本就不要看,除了2之外肯定没有了.
所以eastsun只标记了奇数!.
根据他的我又改了一下变成:
#define PB_ID 69
#include<stdio.h>
#include<time.h>
#define maxn 4000009
int flag[maxn]={0};
int main()
{
int n,m,i,j;
int cnt=1;
flag[2]=1;
for(i=3;i*i<maxn;i+=2)//偶也不里偶数了
{
if(flag[i]==0)
{
cnt++;
for(j=i*i;j<maxn;j+=2*i) flag[j]=1;//注意我上面是写成j+=i显然有的时候j是个偶数.偶也不里了
}
flag[i]=cnt;
}
for(;i<maxn;i+=2)
{
if(flag[i]==0) cnt++;
flag[i]=cnt;
}
for(i=4;i<maxn;i+=2) flag[i]=flag[i-1];
//再把偶数里一下.其实也可以不做这个.完全可以把后面输入的n,m
//转化成奇数的解,结果发现当n,m有小于2的数字时候写起来麻烦.在说要是不加上,跑的比eastsun还快我就不好意思了
//
,毕竟是看了他的才改出来的
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n>m)
{
i=n;
n=m;
m=i;
}
if(n==0) n++;
printf("%d\n",flag[m]-flag[n-1]);
}
return 0;
}
快多了..
[此贴子已经被作者于2007-9-4 13:06:45编辑过]
