求小于N的素数解决方案

求小于N的素数
最近写了个求小于N的素数的程序，感觉效率一般。在i3处理器上求小于100万的素数15秒，小于1千万的素数要5分钟。哪位大神帮改进一下，或者有什么更效率的算法，指点一下。
下面是源代码：
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <time.h>

typedef unsigned long long ULL;
using namespace std;

int main(int args, char *argv[])
{
clock_t start, finish;
double time;
unsigned long long m, n, i;
short f = 1;
vector<ULL> prime;
vector<ULL>::iterator p;
prime.push_back(2);
cin >> n;
i = 3;
start = clock();
while (i <= n)
{
f = 1;
m = sqrtl(i);
for (p = prime.begin(); *p <= m; p++)
{
if(0 == i % *p)
{
f = 0;
break;
}
}
if (0 == f)
{
f = 1;
i += 2;
}
else
{
prime.push_back(i);
i += 2;
}
}
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
//for(p = prime.begin(); p != prime.end(); p++)
//{
// cout << *p << "\n";
//}
cout << endl;
cout << prime.size() << endl;
cout << time << endl;
return 0;
}

------解决方案--------------------
是什么原因？就因为我的是i7的Mac？ 1000w，我才5.26366秒啊。

就是你的代码。
------解决方案--------------------
更效率的算法
--------------
1.以空间换时间
2.WitNess算法，判断素数
------解决方案--------------------
你可以研究一下欧拉筛法
------解决方案--------------------
http://blog.****.net/creazierhit/article/details/7792571
楼主看看这个，我也是别人那儿找的，挺好的所以收藏啦！
------解决方案--------------------

探讨

引用:

是什么原因？就因为我的是i7的Mac？ 1000w，我才5.26366秒啊。

就是你的代码。

我用2个4核处理器的主机还要12秒呢，你那电脑太牛逼了！

------解决方案--------------------
百度 Miller-Robbin 素数测试算法。目前最快的素数测试算法，基于概率论和佛洛依德生日悖论的因子碰撞思想，暴力破解密码的基础算法之一。。。

------解决方案--------------------

探讨

引用:

你可以研究一下欧拉筛法

这个我知道，但是我不清楚这个方法要怎么写程序才能高效率。

------解决方案--------------------
对于一个输入N，计算是否为素数的代码。。。然后你可以吧其中计算过程提取出来放到你的0-N的循环中，然后比较一下1000w的运行时间，，看看能否赶上他的I7，看看数学算法能否战胜硬件？？？

拭目以待，，，

C/C++ code


#include <iostream>  
#include <stdlib.h>  
#include <time.h>  
#include <math.h>  
  
using namespace std;  
  
typedef unsigned long long TYPE;  
  
// 产生随机数  
static bool bInitRandom = false;  
TYPE GetRandomi(TYPE Begin, TYPE End)  
{  
    if (!bInitRandom)  
    {  
        bInitRandom = true;  
        srand((unsigned int) time(NULL));  
    }  
  
    return Begin + rand() % (End - Begin);  
}  
  
// a*b % n求模  
TYPE MultiplyMod(TYPE a, TYPE b, TYPE n)  
{  
    TYPE nReturn = 0 , i ;   
    a %= n;   
    b %= n;  
    for (i = b; i > 0; a = (a << 1) % n, i >>= 1)  
    {  
        if (i & 1)   
        {  
            nReturn = (nReturn + a) % n;  
        }  
    }  
  
    return nReturn;  
}  
  
  
// 获取2进制序列  
int GetBinarySet(bool* pBinarySet, TYPE nNum)  
{  
    int nLen = 0;  
  
    while(nNum)  
    {  
        pBinarySet[nLen ++] = nNum & 1;  
        nNum >>= 1;  
    }  
  
    return nLen;  
}  
  
// 如果结果不为1，则一定是合数，如果结果为1，可能为素数  
TYPE ModularExponetiation(TYPE bigDigit, TYPE b, TYPE n)  
{  
   // 整形变量最多32位，所以可以用32字节存储2进制串， nLen存储长度  
   TYPE nReturn = 1;   
  
   int nLen = 0;  
   bool szbBinarySet[64] = { 0 };    
  
  
   // 获取b的二进制串  
   nLen = GetBinarySet(szbBinarySet, b);  
   for (int i = nLen - 1; i >= 0; i --)  
   {  
       nReturn = MultiplyMod(nReturn, nReturn , n);  
       //nReturn = nReturn * nReturn %  n;  
       if (szbBinarySet[i])  
       {  
           nReturn = MultiplyMod(nReturn, bigDigit, n);  
           //nReturn = nReturn * bigDigit % n;  
       }  
   }  
  
   return nReturn;  
}  
  
bool Witness(TYPE bigDigit, TYPE n)  
{  
    TYPE u = 0, t = 0, x, y, i;  
    // 初始化 u，t  
    // 产生一个奇数u，使得 n - 1 == 2^t * u, t >= 1  
  
    int nLen = 0;  
    TYPE tmp = n - 1;  
    while(tmp)  
    {  
        nLen ++;  
        tmp >>= 1;  
    }  
  
    for (t = nLen -1; t >= 0; t --)  
    {  
        i = 1;  
        for(int j = 0; j < t; j ++)  
        {  
            i <<= 1;  
        }  
  
        if ((n - 1) % i == 0 ) // 若 n -1可以整除  2^t   
        {  
            u = (n - 1) / i;  
  
            // 如果u是奇数则停止  
            if(u % 2 == 1)  
            {  
                break;  
            }  
        }  
    }  
  
    x = ModularExponetiation(bigDigit, u, n);  
    // 测试 x是否为伪素数  
    for (i = 0; i <= t; i ++)  
    {  
        y = MultiplyMod(x, x, n);  
        //y = x * x %  n;  
  
        if (x == 1 && y != 1 && y != n -1)  
        {  
            return true;  
        }  
  
        x = y;  
    }  
  
    if (x != 1)  
    {  
        return true;  
    }  
  
    return false;  
}  
  
bool MillerRabin(TYPE llValue, int nTime)  
{  
   for(int i = 0; i < nTime; i ++)  
   {  
      TYPE a = GetRandomi(1, llValue - 1);  
        
      //a = 20280;  
      if(Witness(a, llValue))  
         return false;  // 肯定是合数  
   }  
     
   return true; // 可能是素数  
}  
  
  
int main()  
{  
   int n;  
   cin >> n;  
  
   TYPE llValue;  
   bool* pIsPrim = new bool[n];  
   memset(pIsPrim, 0, sizeof(bool) * n);  
     
   for(int i = 0; i < n; i ++)  
   {  
      cin >> llValue;  
  
      if (llValue == 2)  
      {  
          pIsPrim[i] = true;  
          continue;  
      }  
      else  
      {  
          if(MillerRabin(llValue, 10)) // 10次蒙特卡洛算法，正确率在99%以上  
          {  
             pIsPrim[i] = true;  
          }  
      }  
   }  
     
   for(int i = 0; i < n; i ++)  
   {  
      if(pIsPrim[i])  
      {  
         cout << "Yes" << endl;  
      }  
      else  
      {  
         cout << "No" << endl;  
      }  
   }  
     
  
   delete[] pIsPrim;  
   return 0;  
}

相关推荐