求小于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.csdn.net/creazierhit/article/details/7792571
楼主看看这个，我也是别人那儿找的，挺好的所以收藏啦！
[解决办法]
[解决办法]
百度 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; }
[解决办法]
之前寫的欧拉筛法
- C/C++ code
#ifndef SOE_HPP#define SOE_HPP#include <bitset>#include <chrono>#include <cmath>#include <iostream>inline void test_sieve_of_eratosthenes(){ typedef std::chrono::time_point<std::chrono::system_clock> TimePoint; TimePoint start = std::chrono::system_clock::now(); size_t const SIZE = 1000000; std::bitset<SIZE> result; result.flip(); result.reset(0); result.reset(1); size_t const finalBit = sqrt(static_cast<double>(SIZE) ) + 1; for(size_t i = 2; i != finalBit; ++i) { if(result[i]) { for(size_t j = i * 2; j < SIZE; j += i) result.reset(j); } } TimePoint end = std::chrono::system_clock::now(); int elapsed_seconds = std::chrono::duration_cast<std::chrono::seconds> (end-start).count(); std::cout << "elapsed seconds = " << elapsed_seconds << std::endl; }#endif // SOE_HPP
[解决办法]
[解决办法]
判断一个数是不是素数有很多定理的
只测试那些可能是素数的数，用通相公式做一个生成器
比如(4n+1), (4n-1)比较容易是素数
然后根据适用范围选择不同的生成器
[解决办法]
记 N = 2*3*5*7*11*13 , 对大于N的数X可以表示为 X = A*N + B , 显然 X 为素数的必要条件是
GCD( N , B ) == 1
起多个线程对不同的 B 做筛法, 完成 100亿以内的筛法在 i5 级别的机器上运行时间应该小于两秒.
2001 年 intfree 的那个筛法程序运行在 PII 500M的机器上, 求100亿以内的素数, 运行时间是 50秒.
求一定范围内的素数个数有 O(N^2/3) 的算法, 求1000亿以内的素数个数也可以秒出.
[解决办法]
[解决办法]