|
|
|---|---|
|
|
|
|
|
不错，一个简单的技巧让空间利用率翻了3.75倍。
|
|
|
|
|
|
我按你说的做了如下修改:
if (isprime(i)) // 如果是质数
{
for (j = i * i; j < MAX_NUMBER; j += i)
nonprime(j); // 将该质数的所有倍数设为非质数
}
结果还是一样, 32/64位分别是2/5秒, 没有差异(或许有0.x秒, time表示不了). 还有, 我是从NEXT_PRIME起到maxfactor, 步进为2, 至少这里循环次数就比你们的算法少了一半, 但时间上.... 
|
|
|
你在这里的改进对你的程序整体影响已经不大了，我说的方法是对梵听版所做的优化，因为你的程序比我们的更复杂，好比我的程序走的是一条筋的直路，你的程序就好比是崎岖小路，虽然这个比喻不大贴切，就象下面两个程序：
for(i=0; i<100; i++) j += i; 和 for(i=0; i<100; i++) if (i%5) j += i; else j *= i; 一样，第一个CPU的流程比较通顺，第二个就会磕磕碰碰。
|
|
|
按你的方法写了个程序，不过我没用到11，只用到5。
#include <stdio.h>
#include <math.h>
#define NUM 50000000
typedef unsigned char BYTE;
BYTE table[NUM/30+1];
void suShu()
{
int i, j, k, u, x, y, z;
int predict[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int xbit[8] = {1, 7, 11, 13, 17, 19, 23, 29};
int flag[30];
int halfNum;
for(i=0; i<30; i++) flag[i] = 8;
for(i=0; i<8; i++) flag[xbit[i]] = i;
table[0] = 1;
halfNum = (int)sqrt(1.0*NUM)-29;
for( j=0,k=0; k<halfNum; j++,k+=30 )
{
for(i=0; i<8; i++)
{
if (((table[j]>>i)&1) == 0)
{
z = k+xbit[i];
u = z%30;
y = z*z;
x = y%30;
for( ; y<=NUM; y+=z)
{
if (flag[x] < 8) table[y/30] |= (1<<flag[x]);
x += u;
if (x >= 30) x -= 30;
}
}
}
}
halfNum += 30;
for(i=0; i<8; i++)
{
if (((table[j]>>i)&1) == 0)
{
z = k+xbit[i];
if (z < halfNum)
{
u = z%30;
y = z*z;
x = y%30;
for( ; y<=NUM; y+=z)
{
if (flag[x] < 8) table[y/30] |= (1<<flag[x]);
x += u;
if (x > 30) x -= 30;
}
}
}
}
for( k=0; k<10; k++) printf("%10d", predict[k]);
for( j=1,k=30; k<=NUM-30; j++,k+=30 )
{
for(i=0; i<8; i++)
{
if (((table[j]>>i)&1) == 0)
{
printf("%10d", k+xbit[i]);
}
}
}
for(i=0; i<8; i++)
{
if (((table[j]>>i)&1) == 0)
{
if ((k+xbit[i]) <= NUM) printf("%10d", k+xbit[i]);
}
}
printf("\n");
}
int main()
{
suShu();
return 0;
}
|
|
|
 谢谢你的优化，看了之后觉得自己写的东西实在太差了，呵呵试着算5亿，才用了20秒，比我以前的40秒根本上一个天一个地！！ |
|
|
|
|
|
[QUOTE=lingyu;633215]若只存储相邻两个素数的差值的一半即(p[k]-p[k-1])/2，
用一个字节一直表示小于304599508537的素数。[/QUOTE] 好主意，在看雪的收获真是不小，“听君一席话，胜读十年书。”  惟一的问题就是用起来有点小小的不爽，每次要经过一定的计算才能得到具体的素数， 瑕不掩瑜，一点小小的损失对于N倍的存储扩展来说还是值得的。 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
