10的10次方内素数求解，挑战基本功

Question

豪杰公司的一道初试问卷题：
求出10的10次方以内的素数,并针对提高效率简要介绍所使用的技巧.
  -请记录程序完成计算所需的时间(我们期望它小于10小时),以及计算机的配置.(缺少这个数据的回答不会被评分.)
  -不需要输出或者保存结果,请在确定一个数是素数的地方用注释标出.
各位XDJM看看有什么高招。
我抛砖引玉先：
首先可以确定一个条件就是，不能被2整除的数，绝对也不可能被2的倍数整除，所以我从3开始验证，步长为2，前提是验证是否可以被2整除。
我的程序运行了接近30小时，才完成。

Answer 1

To:ross33123大侠，能不能讲讲你的具体思路涅，说得太笼统了，呵呵，我觉得是不是提携提携小弟呢？给段代码来研究研究，嘿嘿

Answer 2

const N = 100;
CUIntArray arPrime;

arPrime.Add(3);
int num ;
for(int i = 5 ; i < N ; i+=2)
{
num = arPrime.GetSize(); 
for(int j = 0 ; j < num ; j++)
if(0 == i % arPrime[j] )
break;
if(j == num)
arPrime.Add(i);
}

Answer 3

const N = 1000000;
int *arPrime = new int[100000];

arPrime[0] = 2;
arPrime[1] = 3 ;
int num = 2 ;
for(int i = 5 ; i < N ; i+=2)
{  
for(int j = 1 ; j < num ; j++)
if(0 == i % arPrime[j] )
break;
if(j == num)
arPrime[num++] = i;
}

delete [] arPrime; AfxMessageBox("end!");
10的6次用了二分钟
慢

Answer 4

To:he_zhidan(何志丹:风云伐日)
大侠你的算法的确有点慢了，因为除掉2以外的素数只有两类：一种是除以4余数是1的，如5，13，17等；另外一种是除以4余数是3的，如3，7，11，19等等。
另：嵌套循环的终止条件可以为当前数的平方根，可以减少很大的循环次数，但是即便如此我仍然对我的程序运行速度不满意，虽然每分钟可以运行到4*1000000以上，呜呼呀。
还是希望各位不吝赐教，鞠躬......

Answer 5

DWORD FastCount()
{
INT64 nMax = 1000000l;
CMap<INT64, const INT64&, BOOL, BOOL&> mapResult; DWORD nCount = 2;//1,2
INT64 iStep = 2;
INT64 i = iStep;
while(iStep <= nMax)
{
i += iStep;
if(i <= nMax)
{
mapResult[i] = TRUE;
}
else
{
while(++iStep <= nMax && mapResult[iStep])
mapResult.RemoveKey(iStep);
if(iStep <= nMax)
{
i = iStep;
++nCount;
}
TRACE1("now result %ld\n", iStep);
}
} return nCount;
}使用的是筛选法，10的6次用了一分半钟，机器是K7-600,256M内存，运行期间使用大概4M内存。

Answer 6

To:hjian79(健) 
不知道你有没有看到ross33123大侠说的，嘿嘿，我非常想看看他的代码，哎可惜没有给我。我觉得他说的方法还不错，正在考虑怎么去做涅。

Answer 7

算到 10 的 7 次方2.5 秒#include <stdio.h>
#include <stdlib.h>
#include <windows.h>#define NND 10000000
bool b[NND];int main(int argc, char* argv[])
{
    DWORD start = GetTickCount();
    b[0] = b[1] = 1;
    int i = 2;
    while( i <= NND / 2 )
    {
        int j = i * 2;
        while( j < NND )
        {
            b[j] = true;
            j += i;
        }
        j = i + 1;
        while( b[j] )
            j ++;
        i = j;
    }
    printf("Time elapsed is %d ms.", int(GetTickCount() - start));
return 0;
}

Answer 8

TO: ross33123() 
先谢谢，然后读代码。

Answer 9

上面程序有个小漏洞
        while( b[j] )
            j ++;
改为
        while( j <= NND / 2 &&  b[j] ) 
            j ++;
否则可能溢出，虽然实际运行没有发生问题 :-)

Answer 10

TO: ross33123() 
大侠请问方便给其他的联系方式吗？希望能跟您学习一下，嘿嘿，:P

Answer 11

更清晰的版本 :-)#include <stdio.h>
#include <windows.h>#define NND 10000000
bool b[NND]; // true 表示筛去int main(int argc, char* argv[])
{
    DWORD start = GetTickCount();
    b[0] = b[1] = true;
    int i = 2;
    while( i <= NND / 2 )
    {
        for( int j = i * 2; j < NND; j += i )
            b[j] = true;
        i ++;
        while( i <= NND / 2 &&  b[i] ) 
            i ++;
    }
    printf("Time elapsed is %d ms.", int(GetTickCount() - start));
    return 0;
}

Answer 12

to everyone
我觉得讨论算法的效率有一个前提就是牺牲的空间不能太大，象 ross33123() 的代码中有
#define NND 10000000
bool b[NND]; // true 表示筛去
这样的做法我觉得降低了算法的含金量。
个人看法，不必当真。

Answer 13

TO: BinaryTreeEx(狂徒(完全抵制日货)) 
我同意 完全抵制日货 这个观点，因为我们被日本这个民族所侮辱着，从抗战结束一直到现在他们一直像个婊子一样对美国献媚，而对任何他们伤害过的国家都是高高在上，自认为自己是高等民族而我们是卑劣民族。
我有的时候就在想，为什么我们的国家没有像韩国那样抵制日本呢？为什么不管日本怎么伤害我们，我们总选择沉默呢？
我觉得是我们应该做出点什么的时候了

Answer 14

To：ross33123() 
这种分配内存的方法是无法分配出10的10次方大小的内存来的！！！
所以在我的程序里用的是map分配内存，虽然算法跟你的程序本质是相同，但效率低了，这也是无可奈何之举。

Answer 15

To：hjian79(健) 该说的我上面已经都说了“对时间效率和空间效率的考虑在不同的场合，不同的条件下应该是有所差别的”“这是临时做的简化版本  真的算到 10 次方，就要考虑我上面说的情况”另外你用 map 就能计算到 10 的 10 次方吗（姑且不论时间效率，对内存的要求能得到满足吗）？

Answer 16

To：ross33123() 
算法大家都会，真正要解决的问题是10次方！
如果不能算到10 次方，你的简化版本在这里并没有解决真正的问题啊。

Answer 17

好像有一个叫做Rabin—Miller的素数测试法，我用过，但现在找不到了，这是一个概率测试法，不过应该可以的，而且测试起来速度比较快，不用测试到根号i，只要测试一些就可以确定为素数了，不妨可以试一试。

Answer 18

分块筛法P4 2.4G, Mem=1GN=10^9 Used time=758s, prime number count=50847534Last 50 primes:NO.1 999999937
NO.2 999999929
NO.3 999999893
NO.4 999999883
NO.5 999999797
NO.6 999999761
NO.7 999999757
NO.8 999999751
NO.9 999999739
NO.10 999999733
NO.11 999999677
NO.12 999999667
NO.13 999999613
NO.14 999999607
NO.15 999999599
NO.16 999999587
NO.17 999999541
NO.18 999999527
NO.19 999999503
NO.20 999999491
NO.21 999999487
NO.22 999999433
NO.23 999999391
NO.24 999999353
NO.25 999999337
NO.26 999999323
NO.27 999999229
NO.28 999999223
NO.29 999999197
NO.30 999999193
NO.31 999999191
NO.32 999999181
NO.33 999999163
NO.34 999999151
NO.35 999999137
NO.36 999999131
NO.37 999999113
NO.38 999999107
NO.39 999999103
NO.40 999999067
NO.41 999999059
NO.42 999999043
NO.43 999999029
NO.44 999999017
NO.45 999999001
NO.46 999998981
NO.47 999998971
NO.48 999998959
NO.49 999998957

Answer 19

天，这个速度也太快了吧。
TO：ross33123() 和 Cline(营营) 
两位大侠能不能讲讲二位分块筛分的具体做法啊，最好给兄弟们共享一点代码，偶比较愚钝。哎呀，不要用砖头砸我。
哎，看样子自己真的是笨笨哦，悲哀死。

Answer 20

其实分块只是为了解决过度使用磁盘的问题有 1G 内存的话可能也不用分块了改了一下，算到 10 的 9 次方，用时 152 秒P4 1.6G, 256M  内存Time elapsed is 152031 ms.
last 10 prime numbers:
999999937
999999929
999999893
999999883
999999797
999999761
999999757
999999751
999999739
999999733

Answer 21

#include <stdio.h>
#include <windows.h>#define NND 1000000000
#define SRD 31623
//bool b[NND];
BYTE c[NND / 8 + 1];int main(int argc, char* argv[])
{
    DWORD start = GetTickCount();
    //b[0] = b[1] = true;
    c[0] |= 1; c[0] |= 2;
    int i = 2;
    while( i <= SRD )
    {
        for( int j = i * i; j < NND; j += i )
        {
            if( j%8 == 0 )
                c[j/8] |= 1;
            else
                c[j/8] |= (2 << (j%8-1));
        }
        i ++;
        while( i <= SRD &&  ( c[i/8] & ( i%8 ? (2 << (i%8-1)) : 1 ) ) )
            i ++;
    }
    printf("Time elapsed is %d ms.\n", int(GetTickCount() - start));
    printf("last 10 prime numbers:\n");
    int j = NND - 1;
    for( int k = 0; k < 10; k ++ )
    {
        while( c[j/8] & (j%8 ? (2 << (j%8-1)) : 1) )
            j --;
        printf("%d\n", j);
        j --;
    } return 0;
}

Answer 22

P4 1.6G, 392M  内存 138秒
用的是Sieve地实现方法，感觉效果没有明显的改善。10的10次方没有计算，太麻烦了，要求的空间太大了，要分段计算。不知道有没有其他好的办法。

Answer 23

继续学习中，觉得ross33123大侠公布源代码供给大家学习的无私精神应该得到大家的赞赏，同意的举脚。

Answer 24

#include <stdio.h>
#include "math.h"
//////////////////////////////////////////////////////////////////////////
// Sieve find primes
INT Sieve(UINT nMax)
{
int nCount = 0;

PBYTE pBuffer = (PBYTE)GlobalAlloc(GMEM_ZEROINIT, sizeof(BYTE)*(nMax/8+1));

UINT nLimit = 100000/*sqrt(nMax)*/;
UINT i = 2;

DWORD dwStart = GetTickCount(); //record start timer

for (i = 2; i <= nLimit; ++i) 
{
if (!(pBuffer[i/8] & (1<<(i%8)))) 
{
for (UINT k=i + i; k <= nMax; k += i)
{
pBuffer[k/8] |= 1<<(k%8);
}
}
}


DWORD dwTimer = GetTickCount() - dwStart;

for (UINT j=2; j<=nMax; ++j)
{
if (!(pBuffer[j/8] & (1<<(j%8))))
{
++nCount;
}
}

printf("%d\n", dwTimer);

    for( int k = 0; k < 10; ++k )
    {
        while( pBuffer[j/8] & (1<<(j%8)))
{
            j --;
} printf("%d\n", j);
        j --;
    }

GlobalFree(pBuffer);


return nCount;
}INT main()
{
Sieve(UPPER_RANGE); return 0;
}