[比武] 关于极优的素数算法切磋...
这几天在《一道华为面试题》的帖子里看了一些求素数的算法。但哪个最快尚无定论，我重开个新帖，大家把自己的函数帖过来，大家比比看，谁的最快。
规则：
1。常量
const int MAXNUM = 200000; //求1-200000内的素数，比较时可修改该参数来查看效果
2。格式
每人都把计算完全封装到函数里，以便清晰
不要使用汇编
3。效果
将结果保存到一个数组里，可以在数组中只装：1，3，5，7这样的数，也可以用true,false来标明下标为N的数是否是素数。并且要有输出方法，可以暂时注释掉。已免查看时不方便
输出求解的总时间
例子：//我的求素数函数
通用的常量和头文件：
#include "math.h"
#include "windows.h"
const int MAXNUM = 2000000;
void fun1() //飞天御箭的函数
{
int time = ::GetTickCount(); //进入时开始计时
int *a = new int[MAXNUM/2]; //静态分配太大的数组有问题，改用动态
a[0] = 2;
memset(a+1,0,MAXNUM/2-1);
bool flag;
int n = 0;
for(int i = 3; i < MAXNUM ; i += 2 )
{
flag = true;
for(int j = 0; sqrt(i) > a[j] ; j++)
{
if( i % a[j] == 0)
{
flag = false;
break;
}
}
if(flag) //素数则保存到a
a[n++] = i;
}
// for(i=0;i<n;i++) //输出所有素数
// printf("%d ",a[i]);
time = ::GetTickCount() - time;
printf("\n计算总耗时为:%d\n",time);
}
问题点数：20、回复次数：57Top
1 楼vc_hunter（飞天御箭）回复于 2006-02-13 10:54:29 得分 0
main里直接调用fun1就可知道结果。需要检验算法是否正确，可以把MAXNUM改为2000，把函数里的注释取消。希望大家也按这格式做，以便比较Top
2 楼MarcoCC（成长与不断的跌倒和失败）回复于 2006-02-13 11:45:33 得分 0
这个是我以前写的，楼主可以去测一下看看：
#include <iostream>
#include "windows.h"
const int MAXNUM = 200000;
using namespace std;
void GetPrimeNum(){
size_t num = MAXNUM;
DWORD d1, d2;
d1 = ::GetTickCount();
if (num < 1) {
cout << "error" << endl;
}
if (num == 2) {
cout << num - 1 << " " << num << endl;
}
size_t *IsPrime = new size_t[num];
for(size_t i = 0; i < num; ++i){
IsPrime[i] = 1;
}
for(size_t j = 1; j < num; j += 1){
if (IsPrime[j] == 1) {
for(size_t k = ((j + 1) << 1) - 1; k < num; k += (j + 1)){
IsPrime[k] = 0;
}
}
}
for(size_t p = 0; p < num; ++p){
if (IsPrime[p] == 1) {
//cout << p + 1 << " ";
}
}
delete [] IsPrime;
d2 = ::GetTickCount();
cout << d2 - d1 << endl;
}Top
3 楼Slime_wu（）回复于 2006-02-13 12:02:23 得分 0
加上算法描述就好了，像我这种新手很难搞懂纯代码的算法Top
4 楼vc_hunter（飞天御箭）回复于 2006-02-13 12:04:54 得分 0
你的方法比我的快，你是把所有是不素数的排除掉，我是把素数挑出来- -Top
5 楼Slime_wu（）回复于 2006-02-13 12:08:23 得分 0
lz的算法怎么看着像Eratosthenes筛选法Top
6 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2006-02-13 12:21:28 得分 0
求素数我一直用筛法：
#include<iomanip>
#include<cstdlib>
#include<iostream>
using namespace std;
const int N=10000;
static int a[N];
int main()
{
int i;
for(i=2;i<N;++i)
{
a[i]=1;
}
int m=2;
int count=0;
int k;
while(m<N)
{
if(a[m]==1)
{
cout<<setw(5)<<m;
++count;
k=m;
while(k<N)
{
a[k]=0;
k=k+m;
}
}
++m;
}
cout<<endl;
cout<<"There are "<<count<< "prime number."<<endl;
system("pause");
return 0;
}
Top
7 楼hawkjxr（子陵仲）回复于 2006-02-13 12:24:40 得分 0
直接搜索不就成了，还筛什么?
Top
8 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-02-13 12:41:02 得分 0
如果只是求4G以内的,哪时间肯定是<10秒地, 没什么必要优化了吧, 干脆搞个求 2^40 以内的让大家算算还比较有意思..Top
9 楼CodenameBeta（纯粹马甲）回复于 2006-02-13 13:20:39 得分 0
其实 MracoCC 和 sankt 的算法是一样的...
不过，sankt 的程序有一处严重的错误:
k = m; // 这里应该是 m 的第一个倍数的下标 m << 1
while ( k < N )
{
a[ k ] = 0;
k = k + m;
}
Top
10 楼ikiki（她来听我的演唱会）回复于 2006-02-13 15:38:17 得分 0
我也重贴我的算法:
#include <windows.h>
const int MAXNUM = 2000000;
void fun1() //ikiki
{
int time = ::GetTickCount(); //进入时开始计时
int * include = new int[MAXNUM / 2]; //静态分配太大的数组有问题，改用动态
bool * exclude = new bool[MAXNUM];
int * p = include;
*p = 0;
memset(exclude, 0, MAXNUM);
for (int i=2; i<MAXNUM; ++i)
{
if (!exclude[i])
{
*p++ = i;
for (int j=i; j<MAXNUM; j+=i)
{
exclude[j] = true;
}
}
}
*p = 0;
time = ::GetTickCount() - time;
printf("\n计算总耗时为:%d\n",time);
//for(p=include;*p;++p) //输出所有素数
// printf("%d ",*p);
delete [] include;
delete [] exclude;
}
楼主的算法在我的机器上用了大约 1156 左右的时间，我的算法只要 172 左右的时间。Top
11 楼pagechen（天外飞来的仙）回复于 2006-02-13 15:56:05 得分 0
低于12用直接计算，低于1e^14采用筛选
还有一些其他的大素数计算和测试方法，请参考primreTop
12 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-02-13 16:51:21 得分 0
试试这个：http://maths.diy.myrice.com/download/PrimeNumber.zip （16.1 KB）
比我这个强的话跟我发个email:)Top
13 楼CodenameBeta（纯粹马甲）回复于 2006-02-13 17:16:10 得分 0
楼上的没有源代码？不会是拿数学公式算出来的吧？Top
14 楼yxg80（林夕昱）回复于 2006-02-14 09:50:04 得分 0
learning!Top
15 楼pagechen（天外飞来的仙）回复于 2006-02-14 10:39:04 得分 0
http://www.mersenne.org/prime.htm
这个网站比较有参考价值，数学理论较多Top
16 楼StarGate1（散分.王老五）回复于 2006-02-14 12:28:10 得分 0
筛法最快Top
17 楼chengzanmiao（高薪為共產當多納稅）回复于 2006-02-14 13:59:52 得分 0
我做过华为的这到题，把每个素数装到数组里是最快的。。。
直接就是遍历数组，如果这个数能不数组中的一个整除那就不是素数，不能被数组里全部的书整除那就是素数，继续把他放入数组。由此递推Top
18 楼xxxdg（学习中）回复于 2006-02-14 23:12:10 得分 0
呵呵，
下面从算法上来讲算是比较快的，只是list操作太多，有点耗时间了，嘿嘿，看思想就好。
using namespace std;
unsigned long GetPrime(list<unsigned long> & l,int n,int m)
{
int t=::GetTickCount();
l.clear();
n=n>5?n:7;
for(int i=(n%2)?n:n+1;i<=m;i+=2) if((i%3)&&(i%5))l.push_back(i);
list<unsigned long>::iterator it,iter,pt,pit,pcc;
int x,y;
for(it=l.begin(),pt=l.end(),--pt,y=*pt;x=*it,x*x<=y;it++)
for(iter=l.end(),iter--;x*x<=*iter;)
{
if(!((*iter)%(x))){
pit=iter;
iter --;
if(pit==pt){pt--;y=*pt;}
l.erase(pit);
}
else
iter --;
}
l.push_front(2);
l.push_front(3);
l.push_front(5);
t=::GetTickCount()-t;
return t;
}
Top
19 楼xxxdg（学习中）回复于 2006-02-15 01:22:15 得分 0
换成数组的：
cout<<"Time "<<func2(2000000)的输出结果：
Prime Count 148933
Time 170
-----------------------------------------------------------
unsigned long func(unsigned long int UpBound)
{
int t = ::GetTickCount();
UpBound=(UpBound%2)?UpBound:(UpBound-1);
unsigned long int * Prime= new unsigned long int [UpBound/2+1];
bool * Origin = new bool [UpBound];
memset(Prime,0,UpBound/2+1);
memset(Origin,1,UpBound+1);
unsigned long int i,j,p=0;
for(i=2;i*i<=UpBound;i++)
if(Origin[i])
for(j=i;i*j<=UpBound;j++)
if(Origin[i*j])
Origin[i*j]=0;
for(i=2;i<=UpBound;i++)
if(Origin[i])Prime[p++]=i;
cout<<"Prime count:"<<p<<endl;
t = ::GetTickCount() - t;
delete [] Prime;
delete [] Origin;
return t;
}
Top
20 楼robothn（雷鸟）回复于 2006-02-16 10:55:55 得分 0
#include <iostream>
using namespace std;
#include <windows.h>
#define MAX_NUM 2000000
void main()
{
unsigned int *primes_array = new unsigned int[MAX_NUM/4];
primes_array[0] = 2;
unsigned int primes_found = 1;
int t = ::GetTickCount();
for(unsigned int cur_num = 3; cur_num < MAX_NUM; cur_num+=2)
{
int primes_array_index = 0;
for( ; primes_array_index < primes_found; primes_array_index++)
if( cur_num % primes_array[primes_array_index] == 0 )
break;
if(primes_array_index == primes_found)
{
primes_array[primes_found++] = cur_num;
// cout << cur_num << endl;
}
}
t = ::GetTickCount() - t;
cout << t << "ms" << endl;
delete []primes_array;
}
Top
21 楼terryjwf（开大奔的帅哥）回复于 2006-02-16 12:40:07 得分 0
轻声的问一下：什么是素数？Top
22 楼robothn（雷鸟）回复于 2006-02-16 15:58:08 得分 0
//Count: 148933 Time: 120125ms
#include <iostream>
using namespace std;
#include <windows.h>
//#include <math.h>
#define MAX_NUM 2000000
void main()
{
unsigned int *primes_array = new unsigned int[MAX_NUM/2+1];
primes_array[0] = 2;
unsigned int primes_found = 1, primes_mod_max_index = 0;
int t = ::GetTickCount();
for(unsigned int cur_num = 3; cur_num < MAX_NUM; cur_num+=2)
{
int primes_array_index = 0;
//素数数组每次只需测试到不大于当前数一半的那个素数即可
unsigned int cur_sqrt = cur_num/2;
for( ; primes_mod_max_index < primes_found; primes_mod_max_index++)
if(primes_array[primes_mod_max_index] >= cur_sqrt)
break;
//测试已经存在的素数数组中的元素是否可以整除当前数
for( ; primes_array_index <= primes_mod_max_index; primes_array_index++)
if( cur_num % primes_array[primes_array_index] == 0 )
break;
if(primes_array_index >= primes_mod_max_index)
{
primes_array[primes_found++] = cur_num;
// cout << cur_num << endl;
}
}
t = ::GetTickCount() - t;
cout << "Count:" << primes_found << " Time:" << t << "ms" << endl;
delete []primes_array;
}
Top
23 楼robothn（雷鸟）回复于 2006-02-16 16:20:27 得分 0
//再次优化后结果 Count: 148933 Time: 85844ms
#include <iostream>
using namespace std;
#include <windows.h>
//#include <math.h>
#define MAX_NUM 2000000
void main()
{
unsigned int *primes_array = new unsigned int[MAX_NUM/2+1];
primes_array[0] = 2;
unsigned int primes_found = 1, primes_mod_max_index = 0;
int t = ::GetTickCount();
for(unsigned int cur_num = 3; cur_num < MAX_NUM; cur_num+=2)
{
int primes_array_index = 0;
//素数数组每次只需测试到不大于当前数1/3的那个素数即可
unsigned int cur_sqrt = cur_num/3;
for( ; primes_mod_max_index < primes_found; primes_mod_max_index++)
if(primes_array[primes_mod_max_index] >= cur_sqrt)
break;
//测试已经存在的素数数组中的元素是否可以整除当前数
for( ; primes_array_index <= primes_mod_max_index; primes_array_index++)
if( cur_num % primes_array[primes_array_index] == 0 )
break;
if(primes_array_index > primes_mod_max_index)
{
primes_array[primes_found++] = cur_num;
// cout << cur_num << endl;
}
}
t = ::GetTickCount() - t;
cout << "Count:" << primes_found << " Time:" << t << "ms" << endl;
delete []primes_array;
}
Top
24 楼robothn（雷鸟）回复于 2006-02-16 16:51:25 得分 0
以上是debug 版实测，难怪这么高，我都郁闷了。
release 版 1297ms - 1360ms 之间
另：ikiki 的算法是典型的空间换时间做法，数大时存储要求很大Top
25 楼A_B_C_ABC（黄瓜@YouCanDoIt）回复于 2006-02-16 17:37:37 得分 0
//20000 用时：0
//200000 用时：62
//2000000 用时：906 921 921
//20000000 用时：23250
#include <iostream>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cmath>
using namespace std;
struct node
{
int Jiange;
node* next;
};
node head[8];//消去2，3，5的倍数
int *pint=NULL;//存放素数的数组指针
bool isPrime(int n)
{
int *p=pint+3;//*p==7
int nn=sqrt(n);
for(int i=7;i<=nn;i=*p++ )
{
if(n%i==0) return false;
}
return true;
}
void prime(int count)//要求count>7
{
//初始化全局数组，并连接为循环链表。
head[0].Jiange=4;
head[1].Jiange=2;
head[2].Jiange=4;
head[3].Jiange=2;
head[4].Jiange=4;
head[5].Jiange=6;
head[6].Jiange=2;
head[7].Jiange=6;
head[0].next=head+1;
head[1].next=head+2;
head[2].next=head+3;
head[3].next=head+4;
head[4].next=head+5;
head[5].next=head+6;
head[6].next=head+7;
head[7].next=head;
node * pNode=head+7;
int* p=pint;
*p++=2;//这三个数硬给
*p++=3;
*p++=5;
for(int number=7;number<=count;number+=pNode->Jiange)
{
if(isPrime(number))
{
*p++=number;
}
pNode=pNode->next ;
}
*p=0;
}
void main()
{
clock();
int count=2000000;//修改这里输出素数的上限
//pint =new int [count/3];//只要count>=39,就不会出错，
pint =new int [count/2];//欲求上限<39的素数，数组要分大点
prime(count);
//for(int *p=pint;*p!=0;++p)
// cout<<setw(10)<<*p;
delete [ ]pint;
cout<<endl<<"用时："<<clock()<<endl;;
}Top
26 楼robothn（雷鸟）回复于 2006-02-16 18:08:17 得分 0
错了，上面release 版时间是 vc_hunter (飞天御箭) 的
我自己的是 84344ms ，惨Top
27 楼icenl（成冈【我不要分，不要给我】）回复于 2006-03-23 00:45:53 得分 0
不错Top
28 楼Jiana（Robin.English）回复于 2006-03-23 19:51:54 得分 0
我所知道的最快的是Eratosthenes筛选法。目前也是。
其应用于加密解密领域Top
29 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-03-25 01:24:59 得分 0
刚写的一个极端失败的代码, 基本没有优化, 分段也很不合理, 内存越界也没管就多分配了N多的内存让它随便越着玩, 比几年前 intfree 的代码慢了很多, slove 运行后 WBUF 保存着哪些数是素数的状态, 木写文件, 什么时候无聊了把 1E14 内的素数算出来存盘上:
................................................................................
PI ( 10737767040 ) == 487040244
TIME USED: 64812
Press any key to continue
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
using namespace std;
#ifdef _MSC_VER
typedef unsigned __int64 QW;
ostream& operator<< ( ostream& os , const QW& d ) { char _buf[64]; sprintf( _buf , "%I64d" , d ); return os << _buf; }
#else
typedef unsigned long long QW;
#endif
typedef unsigned DW;
typedef unsigned char BY;
const DW XXXX = 16 * 3 * 5 * 7 * 11 * 13;
const DW PPPP[] = { 3 , 5 , 7 , 11 , 13 };
const DW FFFF = ( 17 - 3 ) / 2;
const DW DXXX = XXXX / 2;
const DW BLEN = XXXX / 16;
int BBC[256];
DW PCNT = 1; // 2.
BY TBUF[ BLEN * 10 ];
BY *FPNM = TBUF + 16;
BY *FBUF = FPNM + 32 + BLEN;
BY *WBUF = FBUF + 48 + BLEN;
void init()
{
QW i ,j ,k , n = sqrt( XXXX ) / 2;
for( i = 0; i < 256; ++i )
{
for( j = 0; j < 8; ++j )
if( !(i&(1<<j)) )
++BBC[i];
}
FPNM[ BLEN - 1 ] = 0x80;
for( i = 0; i <= n; ++i )
{
if( FPNM[i/8] & ( 1 << (i % 8 ) ) ) continue;
k = 2 * i + 3 ;
for( j = ( k * k - 3 ) / 2 ; j < DXXX ; j += k )
FPNM[j/8] |= 1 << ( j % 8 );
}
for( i = 0; i < BLEN ; ++i )
PCNT += BBC[ FPNM[i] ];
for( i = 0; i < sizeof( PPPP ) / sizeof( PPPP[0] ); ++i )
{
for( j = (PPPP[i] - 1) / 2 ; j < DXXX; j += PPPP[i] )
FBUF[ j / 8 ] |= 1 << ( j % 8 );
}
}
DW slove( QW s )
{
QW i , j , k , f = s * XXXX + 1; QW n = sqrt( f + XXXX ) / 2;
memcpy( WBUF , FBUF , BLEN );
for( i = FFFF; i < n ; ++i )
{
if( FPNM[i/8] & ( 1 << (i % 8 ) ) ) continue;
k = 2 * i + 3;
if( k * k < f )
{
j = ( (f - 1) / k + 1 ) | 1 ;
j = ( k * j - f ) / 2;
}
else
j = ( ( k * k ) - f ) / 2;
#if 0
for( ; j < DXXX ; j += k )
{
WBUF[ j / 8 ] |= 1 << ( j % 8 );
}
#else
__asm
{
mov eax , WBUF;
mov ebx , DXXX;
mov ecx , DWORD PTR j;
mov edx , DWORD PTR k;
}
__loop_here:
__asm
{
BTS [eax] , ecx;
add ecx , edx;
cmp ecx , ebx;
jb __loop_here;
}
#endif
}
for( i = 0 , j = 0; i < BLEN ; ++i )
j += BBC[ WBUF[i] ];
return j;
}
int main()
{
clock_t t = clock();
init();
QW r = PCNT , s = 1 + (QW(10)<<30)/XXXX , nn = s / 80;
for( QW i = 1; i <= s; ++i )
{
if( i % nn == 0 ) cout << "." << flush;
r += slove( i );
}
cout << "PI ( " << i * XXXX << " ) == " << r << endl;
cout << "TIME USED: " << clock() - t << endl;
return 0;
}
Top
30 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 15:12:49 得分 0
记 f(n) = (n+1)* phi(10^n)，则
f( 1) = 2 * 4 = 8
f( 2) = 3 * 25 = 75
f( 3) = 4 * 168 = 672
f( 4) = 5 * 1229 = 6145
f( 5) = 6 * 9592 = 57552
f( 6) = 7 * 78498 = 549486
f( 7) = 8 * 664579 = 5316632
f( 8) = 9 * 5761455 = 51853095
f( 9) = 10 * 50847534 = 508475340
f(10) = 11 * 455052511 = 5005577621
f(11) = 12 * 4118054813 = 49416657756
f(12) = 13 * 37607912018 = 488902856234
f(13) = 14 * 346065536839 = 4844917515746
f(14) = 15 * 3204941750802 = 48074126262030
若将 10^14 内的所有素数以字符形式存盘，需要的字节数为：
f(1)+f(2)+...+f(14) = 53462935128392 = 2 ^ 45.6036... = 48.6 TB（1T=2^40）
所以楼上的“什么时候无聊了把 1E14 内的素数算出来存盘上”可不是那么容易实现的，即便采用了高级压缩方式。
在无法逐一保存素数的前提下，我们一般关心的是n以内的素数个数phi(n)；或某个范围内的具体素数；或判定某个大整数是否为素数。
我最近将两年前设计的 PrimeNumber 进行了全面优化（可谓是“精雕琢细”也），使可执行文件比先前更小（16.0 KB），但效率更高！举例来说，在 P4 1.7GHz CPU 上，输出 10000000 以内的素数（共 5,761,455 个）到文件，以前需 528994μs，现仅需 152619μs，效率提高了数倍！新版将随 HugeCalc 于数月后一并升级公开发布，敬请关注。（现提供Release Candidate版：http://maths.diy.myrice.com/download/PrimeNumber(RC).zip (12.3 KB)）
该套程序许多核心技术是我自创的，等哪天我有空时，可能会选几则整理给大家共享（放在我的个人主页上）；如果心情格外好（或格外差）的话，也许会直接公开源代码。。。Top
31 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 15:35:16 得分 0
对不起，f(n) 的定义有误，应为：f(n) = ( n + 1 ) * ( phi(10^n) - phi(10^(n-1)))，
所算数据应略小，但不影响后面的阐述。Top
32 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-03-30 17:08:51 得分 0
嘻嘻, 楼上的分析明显有问题, 我只需要存这些数据 PI( N * XXXX ) 也就基本上肯定用不了 2G , 实在觉得还太大的话我就分段分大点 , 有了这些数据, 最多的时候筛一段就可以知道 第几个素数是什么或者是一个范围内有多少素数, 也就几个毫秒的时间, 对我而言就够用了.Top
33 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 17:23:19 得分 0
phi(10^14)/2G = 1528235.3166... 感觉这个信息压缩比不太可能，
除非你仅仅为了计数，
或是在需要时再筛出来（那就仅需纪录phi(10^7)上的信息了，两者差好几个数量级了）Top
34 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-03-30 18:23:51 得分 0
我不是说了么, 我只记录 PI( N * XX , (N+1) * XX ) 又不记录具体素数, 肯定 1G 都用不到.
就做的像 http://primes.utm.edu/nthprime/index.php 就可以了.
10^7 的素数大家都知道不用存的, 反正算一下也用不了多少时间.Top
35 楼whbo（王红波（年轻人，要有所作为））回复于 2006-03-30 18:57:37 得分 0
delphi社区也做了这个题，2000000以内，好象1.4s就够的，下面是别人的处理代码
累计毫时：1.419秒
var
PrimeNumbers: array[2..1000000] of integer;
procedure getPrimeNumber;
var
i, j: integer;
begin
for i := low(PrimeNumbers) to high(PrimeNumbers) do
PrimeNumbers[i] := i;//初始化
for i := low(PrimeNumbers) to trunc(sqrt(high(PrimeNumbers))) do
if PrimeNumbers[i] > 0 then
for j := i + 1 to high(PrimeNumbers) do
if PrimeNumbers[j] > 0 then
if PrimeNumbers[j] mod PrimeNumbers[i] = 0 then
PrimeNumbers[j] := 0;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
sum: int64;
i: integer;
begin
getPrimeNumber;
sum := 0;
for i := low(PrimeNumbers) to high(PrimeNumbers) do
if PrimeNumbers[i] > 0 then
sum := sum + PrimeNumbers[i];
showmessage(inttostr(sum));
end;
我的机器P4 1.8 WIN 2K/512MTop
36 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 19:25:29 得分 0
to DiabloWalkOnTheEarth:
“我不是说了么, 我只记录 PI( N * XX , (N+1) * XX ) 又不记录具体素数, 肯定 1G 都用不到.”
——这我知道，但这不是保留数据，而是程序，并非你当初的“什么时候无聊了把 1E14 内的素数算出来存盘上”说法了（该话题无甚意义，就此打住）。。。
to whbo:
用我上面给出的程序，统计并输出 2000000 以内的素数，全过程不超出 10 毫秒！Top
37 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-03-30 20:08:39 得分 0
这东西对你来说是毫无意义, 但对我来说是我需要的全部东西, 大家关心的东西不同罢了.对我来说 一个东西是1毫秒还是100毫秒是没有区别的.
1E14的结果要存下来也算不上困难, 算了一下, 不过用小于2.5T的空间罢了, 也花不了几块硬盘.Top
38 楼wofish2（）回复于 2006-03-31 15:41:04 得分 0
markTop
39 楼Kache（雁一声）回复于 2006-03-31 17:39:42 得分 0
我看了gxqcn的程序，首先说一句，的确很快。但是稍微观察一下，就知道所用的方法并不是依赖于所选择区间的大小，这一点似乎是很神奇的，因为这需要依赖于某个算法，而它可以判断一个数是否质数。据我所知，这样的算法似乎并不存在。当然在群论中有一个比较高效的算法，只是判断的结果并不是绝对准确的。
以上个人意见，期待gxqcn能以源码澄清之。
再者gxqcn的程序似乎是用汇编写的吧。
Top
40 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-03-31 19:48:55 得分 0
筛法求素数本来复杂度就不高, 应该只稍微高于 O ( N ) , 如果只是求素数个数记得仅为 O ( N ^ (2/3) ) 左右 , 求 4G 以内素数本来就基本不要时间, 就是比输出的速度了 ....
Top
41 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-31 21:30:24 得分 0
刚刚对该程序新增加了一个功能：在输出窗口中通过“ToolTip”形式显示生成素数实际耗时（整个界面中最多可同时反映三个计时：统计数目计时、生成素数计时、字符输出计时）。
程序大小由原来的 16.0 KB → 16.5 KB，压缩包则由 12.3 KB → 12.7 KB，这是唯一的负作用。
DiabloWalkOnTheEarth 所言极是，所以我才在输出上花了很大功夫（估计现在尚未有人可以超出，可能说大话了，别见怪）；
谢谢 Kache 的夸奖，我的程序中只有数行汇编代码，没有用任何浮点代码（开方运算都是自己实现的）。前面已有说明，我的算法主要分三部分：统计、生成、输出，每部分都经过了高度优化。
为了让大家提前体验，现提供 PrimeNumber 的 Release Candidate 版(12.7 KB)：
http://maths.diy.myrice.com/download/PrimeNumber(RC).zip
请将上述链接复制到地址栏，按回车即可下载（有效期截至到其正式版发布；基本不再作修订）。
两年前我为了开发高效的阶乘算法，需要快速生成素数算法，整个“五一”假日我都在开发调试这个“PrimeNumber”，直到满意为止。可以说，该程序只是 HugeCalc 开发过程中的一个副产品，但估计对很多人有用，所以我特地将它独立出来与大家共享。
在公开发布后，许多网友惊诧于它们的速度和性能，纷纷来信询问算法。也许碰巧的是，求阶乘、筛素数正好是老师布置作业热衷选题吧？:)这类题目上手都不难，但不同的算法效率简直有天壤之别！之前我曾将阶乘算法的核心思想整理了一下放在了我的个人主页里，现在已被一些网站转载；我打算近期再整理一篇关于我这个 PrimeNumber.exe 的文章，只是现在较忙，不知何时可兑现，亦不知有多少人感兴趣。。。也许到时会直接公开源代码，但我认为终归没有给出说明文档更易让人接受。。。Top
42 楼littlegang（Gang）回复于 2006-03-31 21:50:27 得分 0
就普通方法而言，筛选法里
居然有大家都没有想到的一个优化， 对于 MAX ＝ 2 就不考虑了，从 3 开始的
就是：
数组里面只要存奇数就可以了，筛选时每次 步长 不是m，而是2m ， 就是m，3m，5m，7m，9m去除Top
43 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-03-31 22:48:15 得分 0
这个东西你看到谁去用 2 筛过, 最基本的你也得先用 2 3 5 7 11 13 等等几个小素数先筛一遍Top
44 楼Kache（雁一声）回复于 2006-03-31 23:04:14 得分 0
DiabloWalkOnTheEarth似乎误会了，试问用筛法求4G之内的素数和求3G到4G之间的素数所需时间是否相同？再者“求4G以内素数本来就基本不要时间”，那么“基本不要时间”是多少时间呢？Top
45 楼Kache（雁一声）回复于 2006-03-31 23:08:05 得分 0
DiabloWalkOnTheEarth：
“这个东西你看到谁去用 2 筛过, 最基本的你也得先用 2 3 5 7 11 13 等等几个小素数先筛一遍”
——我从不认为这种手法也算优化，那如此说来也可以先算出1M之内先存个表再说咯。Top
46 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2006-04-01 08:34:00 得分 0
记 N = 2 * 3 * 5 * 7 * 11 * 13 ; 对 X = K * N + B , K >= 1 的数, 显然只有 ( N , B ) = 1 的数才会是素数, 所以你就只需要在 K * N + 1 , K * N + 17 , K * N + 19 .... 这种形式的数里筛选素数, 而不用考虑 K * N + 2 , K * N + 3 ... K * N + 15 .... 等等形式的数, 就这样简单的处理, 可以使运算量减少到基本算法的 1/5 左右.
求4G以内素数本来就基本不要时间, 那么“基本不要时间”是多少时间呢?
-----------------------------------------------------------------
< 10 秒.
试问用筛法求4G之内的素数和求3G到4G之间的素数所需时间是否相同？
-----------------------------------------------------------------
当然不同, 不是说了复杂度大概是 O ( N ) 么, 准确点应该在 O ( N * lnlnN ) 左右, 前者需要的时间大概是后者的 4 倍.Top
47 楼yhmhappy2006（Nathan）回复于 2006-04-01 09:26:23 得分 0
楼主,看看下面这个函数吧
int GetPrime(int *a)//飞天御箭的函数
{
a[0] = 2;
memset(a+1,0,MAXNUM/2-1);
bool flag;
int n = 1;
int sqt = 0;
for(int i = 3; i < MAXNUM ; i += 2 )
{
flag = true;
sqt = (int)sqrt(i);
for(int j = 0; a[j] < sqt+1; j++)
{
if( i % a[j] == 0)
{
flag = false;
break;
}
}
if(flag)//素数则保存到a
a[n++] = i;
}
return n;
}
与你首发的比一下有什么不同,再看看执行效率有什么巨大的提高?
调用:
DWORD d1, d2;
d1 = ::GetTickCount();
n = GetPrime(a);
d2 = ::GetTickCount();
cout << "Use time: " << d2 - d1 << endl;Top
48 楼yhmhappy2006（Nathan）回复于 2006-04-01 09:50:35 得分 0
to: sankt(黄景天)
请看你的程序的优化版,只加了一句,找找看是哪句
int GetPrime(int *a)//use time : 550
{
cout << "f3" << endl;
int i;
a[0] = a[1] = 0;
for(i=2; i<MAXNUM; ++i)
{
a[i]=1;
}
int m=2;
int count=0;
int k;
while(m < MAXNUM)
{
if(a[m]==1)
{
//cout<<setw(5)<<m;
++count;
k=m;
while(k < MAXNUM)
{
if(a[k]!=0)
a[k]=0;
k=k+m;
}
}
++m;
}
return count;
}
调用:
int *a = new int[MAXNUM];//静态分配太大的数组有问题，改用动态
DWORD d1, d2;
d1 = ::GetTickCount();
n = GetPrime(a);
d2 = ::GetTickCount();
cout << "Use time: " << d2 - d1 << endl;
Top
49 楼iicup（双杯献酒）回复于 2006-05-28 08:10:43 得分 0
建议
//for(i=0;i<n;i++)//输出所有素数
//printf("%d ",a[i]);
time = ::GetTickCount() - time;
修改成:
time = ::GetTickCount() - time;
//for(i=0;i<n;i++)//输出所有素数
//printf("%d ",a[i]);
输出时间不应该计算成计算时间。
实际上，在数据不太的情况下，
输出时间占据总时间的 95% 以上。
以楼主的例子看，
不输出
// 计算总耗时为:1719
有输出
// 计算总耗时为:57265
1719 / 57265 = 0.03Top
50 楼FengYuanMSFT（(6.4 被封杀)袁峰 http://fengyuancom.spaces.live.com）回复于 2006-05-28 09:13:58 得分 0
那个程序最快?Top
51 楼iicup（双杯献酒）回复于 2006-05-28 10:09:16 得分 0
强烈建议不包括输出的时间，
发现输出时间和控制台屏幕的大小强烈相关！！
下面是我的一个测试：
窗口最大化
总计36192个素数
计算总耗时为:23656
窗口最小
总计36192个素数
计算总耗时为:1078
相差达20倍以上，呵呵。
Top
52 楼iicup（双杯献酒）回复于 2006-05-28 10:18:41 得分 0
// 用筛法求素数
/*
Realse 版
不输出素数到屏幕
总计36192个素数
计算总耗时为:141
*/
#include "stdafx.h"
#include <windows.h>
#include <math.h>
const int MAXNUM = 2000000;
void fun1();
int _tmain(int argc, _TCHAR* argv[])
{
fun1();
return 0;
}
// 质数判断
bool IsPrime(int nData,const int* pPrime)
{
int nGeneMax = sqrt(nData*1.0);
while(*pPrime <= nGeneMax)
{
if((nData % *pPrime) == 0)
{
return false;
}
pPrime++;
}
return true;
}
// 返回素数个数
// 要求nMax>=6
int Prime(int nMax)
{
// 素数个数
int nPrimeNum = 3;
// 存储素数
int *pPrime = new int[nMax];
memset(pPrime,0,nMax*sizeof(int));
pPrime[0] = 2;
pPrime[1] = 3;
pPrime[2] = 5;
// 当前素数区间
int* pPrimeSection = pPrime;
int nPrimeSection = 2;
int nData = 0; // 待判定的数
bool bContinue = true;
while(bContinue)
{
pPrimeSection++;
nPrimeSection *= pPrimeSection[0];
for(int k=1;bContinue && (k<pPrimeSection[1]);k++)
{
// +1
if(IsPrime(k * nPrimeSection + 1,pPrimeSection))
{
pPrime[nPrimeNum++] = k * nPrimeSection + 1;
}
// +i
for(int* pM = pPrimeSection+1; pM[0]<nPrimeSection; pM++)
{
nData = k * nPrimeSection + *pM;
// 停止判断
if(nData > nMax)
{
bContinue = false;
break;
}
if(IsPrime(nData,pPrimeSection))
{
pPrime[nPrimeNum++] = nData;
}
}
}
}
//输出所有素数
//for(int i=0;i<nPrimeNum;i++)
//{
// printf("%d ",pPrime[i]);
//}
delete[] pPrime;
pPrime = 0;
return nPrimeNum;
}
void fun1()
{
// 开始计时
int time = ::GetTickCount();
// 计算
int nNum = Prime(MAXNUM);
// 计时结束
time = ::GetTickCount() - time;
printf("\n总计%d个素数",nNum);
printf("\n计算总耗时为:%d\n",time);
}
Top
53 楼iicup（双杯献酒）回复于 2006-05-28 11:02:50 得分 0
我发觉我的算法是错误的。
汗...Top
54 楼cattlenzq（吃狼的豆腐（不要给分了，散起来真麻烦！））回复于 2006-05-28 11:18:39 得分 0
感觉还是把以前算过的全都存起来快啊Top
55 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-05-31 09:50:54 得分 0
在最新版的 HugeCalc.dll V6.x 中已提供了 PrimeNumber.exe 程序相应导出接口，欢迎使用。
HugeCalc.dll V6.x 还具备超大整数素性测试、随机生成素数等功能。下载地址：
http://maths.diy.myrice.com/download/HugeCalcV6000b.rar （1.48 MB）Top
56 楼iicup（双杯献酒）回复于 2006-06-02 00:12:32 得分 0
现在，素数判断已经有
(1)在数学上已经证明正确的，复杂度略微大于多项式级的算法．
(2)其正确性依赖一个尚未证明的猜想，复杂度等于多项式级的算法.
因此，在实际使用中，如果你对那个猜想（广义黎曼猜想）有充分的信心，
则可以认为这个问题已经被作为P类问题解决．
在这个意义上，一个程序只是给出结果，实际上没有任何数学上的意义．
甚至程序本身使用不可靠的费马小定理为基础的判断(这种方法是对某些特殊合数会错误地被判断为质数)，也能通过验证.因为要找一个大的伪素数并不容易．Top
57 楼luvybird（）回复于 2006-06-02 00:27:38 得分 0
学习Top
