| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 716 人关注过本帖
标题:[原创]浅谈素数
取消只看楼主 加入收藏
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
结帖率:100%
收藏
 问题点数:0 回复次数:1 
[原创]浅谈素数

何为素数,一般想到的就是不能被比他小的数所能整除的数,再进一步想,不能被比他的一半小的数所能整除的数,再进一步,不能被比他的平方根小的数所能整除,能否再优化呢?答案是肯定的,如果一个数不能被比他小的所有素数整除,这个数就是素数,这是素数真正的定义,只要考虑素数就可以了,和上面的结合起来就是如果这个数不有被比他的平方根小的所有素数整除,这个数就是素数.下面是我曾经写的一个程序,用来求m到n之间的素数个数,n小于1000000,如果要更大,就将N改大点,数组a再定义大点即可,求0到1000000的所有素数个数可在一秒内得到结果.


#include<stdio.h>
#include<math.h>
#include<time.h>
#define N 1000
int a[168]={2};
void init(void) //求出1000以内的所有素数,储存在数组中
{
int i,j,k=1,sure=1;
for(j=3;j<N;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
}

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

以上是为了节约空间.如果你认为空间足够大,那么用以下方法即可高效的得到结果(就是所为的筛法求0到1000000内的素数个数,本机测试只需125MS左右,0到10000000内的要1391MS,如果想求更大的,只要将N改得更大即可,不过也有范围,最大值可能与机器有关)

#include<stdio.h>
#include<time.h>
#define N 10000000
int a[N];
void prime(long n) //用筛法将不是素数的值置0
{
long i,j;
a[1]=0;
for(i=2;i<n;i++)
a[i]=1;
for(i=2;i<n/2;i++)
if(a[i])
for(j=i*2;j<n;j=j+i)
a[j]=0;
}
int main()
{
int m,n,sum,i;
clock_t start,finish;
while(scanf("%d",&n))
{
start=clock();
prime(n);
sum=1;
for(i=3;i<=n;i++)
if(a[i])
sum++;
printf("%d\n",sum);
finish=clock();
printf("%lf\n",(double)(finish-start));
}
return 0;
}

为了让程序消耗内存更少,由于数组中储存的只是1和0,所以用最小的储存类型储存,所以我用C++改为bool型(另一种更优的办法是用位段来处理),另外不用储存偶数的情况,所以对比INT(32位)内在减少了8倍,而在效率上我也优化了3倍左右,具体程序如下:

#include<iostream>
#include<time.h>
#define N 100000000
bool a[N];
using namespace std;

void prime(unsigned long n) //用筛法将不是素数的值置0
{
unsigned long i,j;
a[0]=1; //2是唯一的偶素数,另作打算
for(i=3;i<=n;i+=2) //将大于2小于或等于n的奇数
a[i/2]=1;
for(i=3;i<=n/3;i+=2) //只要考虑小于n/3的就可以了,因为乘以2就是偶数,至少也是乘以3,

大于n/3的就不用判断
{
if(a[i/2])
for(j=i*3;j<=n;j+=2*i) //j的奇数倍的数全部筛选出去
a[j/2]=0;
}
}
int main()
{
unsigned long n,sum,i;
clock_t start,finish;
while(scanf("%d",&n))
{
start=clock();
prime(n);
sum=1;
for(i=3;i<=n;i+=2)
if(a[i/2])
sum++;
cout<<"the number of the prime less than n is "<<sum<<endl;
finish=clock();
cout<<"the promgram expends "<<(double)(finish-start)<<"ms"<<endl;
}
return 0;
}



如果有更优的算法,希望分享一下

[此贴子已经被作者于2007-8-29 8:15:16编辑过]

搜索更多相关主题的帖子: 素数 平方根 整除 定义 
2007-04-28 21:00
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
素数就是这样定义的怎么会不对呢

雁无留踪之意,水无取影之心
2007-04-29 13:01
快速回复:[原创]浅谈素数
数据加载中...
 
   



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

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