密码破解中对于计算的要求比较，所以最基本的要求是算法简单快速。对于RSA大数分解中，经常用到求素数，对于大素数的生成，需要用到一些概率性算法，所以要对算法生成的P进行基本的验证。为了使算法不犯低级的错误，最基本的是用小素数表进行检验。
对于小素数的生成（以下用2^23内全部素数为例），数域筛法是快速有效的。但是传统的筛法对于个人的计算机来说，需要很长的时间，甚至一天一夜也无法算出。所以我做了些改进，原始的筛法简单的比较了一下。
采用两种方法进行，分别是传统的试除法和埃拉托斯特尼(Eratosthenes）筛法，也就是数域筛法。
1．传统的试除法基本思想很简单，在判断n是否是素数时，用作除数的所有整数都小于【根号n】（郁闷，连基本的数学符号都打不出来，建议斑竹们向领导们提议一下，增添这个功能） ，如果这些数中的某任意一个数可以整除n，那么n就不是素数（整数2除外）。这样逐个生成，直到所要求的上限。
这种算法可以通过只检验奇数来改进，但总体来说是效率非常低的算法。实验的程序比较简单，其伪码可以表示如下：
Test(n)
{
r←2
while (r< )
{
If(r∣n)return “合数”
r←r+1
}
return “素数”
}
分析算法的复杂度，如果假定每一个算术运算只用一比特的操作（不是实际的运算），那么这个算法的比特运算复杂度就是【2的nb次幂后再开平方】--表达一个指数幂真复杂……         其中nb是n的比特数，可以表示成为O(【2的nb次幂后再开平方】)，如果n非常大的时候，这种算法是不可能的。这还只是判断一个素数。对于生成2^23以下所有素数，计算量是非常大的。
2．埃拉托斯特尼(Eratosthenes）筛法的具体做法是，先把n个自然数按次序排列起来。1不是素数，也不是合数，要划去。第二个数
2是素数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留 下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后 面所有能被5整除的数都划去。这样一直做下去，就会把不超过n的全部合数都筛掉，留下的就是不超过n的全部素数。
针对这种算法，本组分别做了两种实验。
实验（1）的主要代码如下：
void PrimeNumber2()
{
     int Max[MAX_NUMBER/2];
     memset(Max,0,MAX_NUMBER);
     Max[0] = 2;     int cout = 1;
     bool bflag = true;
     for(int i = 3; i < MAX_NUMBER; ++i)
     {
         bflag = true;
         for (int j = 0; j < cout; ++j)
         {
              if(i%Max[j] == 0)
              {
                   bflag = false;
                   break;
              }
         }
         if(bflag)
         {
              Max[cout++] = i;
         }
     }
}
实验（1）在判断过程中用到的除法，我们知道在计算机中做除法的运算总是速度慢的，所以在实验生成2^23以下全部素数时，运算的时间非常长，甚至是几个小时也很难完成。
实验（2）做了以下改进，首先对于偶数除2以外都不是素数，程序可以只针对奇数运算。将除法改为乘法来判断，只检测到【根号n】 。实验主要程序如下：
void prime()
{

        clock_t start, finish;
        start = clock();
        char *primes = new char[MAX_NUMBER+1];
        for( int i=0; i<MAX_NUMBER; i=i+2)
                primes[i] = '0';
        for( int i=1; i<MAX_NUMBER; i=i+2)
                primes[i] = '1';
        primes[1] = '0';
        primes[2] = '1';
        primes[MAX_NUMBER] = '\0';
        int M = (int)sqrt((float)MAX_NUMBER);
        for( int i=3; i<=M; )
        {
                int b=0;
                for( int n=3; ; n=n+2)
                {
                        b = n*i;
                        if(b>=MAX_NUMBER)break;
                        primes = '0';
                }
                do
                {i++;}
                while( primes[i] !='1');
        }
        primes[MAX_NUMBER] = '\0';
        finish = clock();
        double duration = (double) (finish - start)/ CLOCKS_PER_SEC;
        printf( "%2.1f seconds\n", duration );
        cout<<"保存文件"<<endl;
        FILE *fp;
        fp = fopen("primes.txt","w");
        for(int i=0;i<MAX_NUMBER;i++)
        {
                if( primes[i] =='1')fprintf(fp,"%d ",i);
        }
        delete []primes;
        fclose(fp);
int _tmain(int argc, _TCHAR* argv[])
{
        prime();
        return 0;
}
运行后得到的实验结果非常理想，生成2^23以下全部素数只用了0.3秒。得到了非常大的改善和提高。

主要是改变除法的基本测试，不妥之处，请大家批评。或者是有更好的方法的，请告诉我。
邀请码已发，在此谢谢版主！！

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)