本文共 1335 字，大约阅读时间需要 4 分钟。
包括线性筛，朴素判断方法，以及miller-rabin（非加强版）
#include #include #include #include using namespace std;inline bool sqrt_judge(int x) //复杂度O(sqrt(n)){ if(x == 2) return 1; if(x == 1) return 0; for(int i = 2; i*i <= x; i++) if(x % i == 0) return 0; return 1;}inline int Pow(int x, int P){ int ans = 1; for(int i = 1; i <= P; i++) ans = ans*x%(P+1); return ans;}inline bool Miller_Rabin(int x) //不稳定随机判断，复杂度O(1){ if(x == 2) return 1; if(x == 1) return 0; int p[7] = { 2, 3, 5, 7, 11, 13, 17}; for(int i = 0; i < 7 && p[i] != x; i++) if(Pow(x, p[i]-1) != 1) return 0; return 1;}vector prime;map check;void Select() //素数筛，筛选复杂度O(n)，判断复杂度O(1){ prime.clear(); check.clear(); for(int i = 2; i <= 100000; i++) { if(! check[i]) prime.push_back(i); for(auto x : prime) { if(i * x > 100000) break; check[i * x] = 1; if(i % x == 0) break; } }}int main(){ Select(); int n; while(cin>>n) { int ans = 0, i; switch(rand()%3) { case 0: for(i = 1; i < n; i++) if(sqrt_judge(i)) ans += i; break; case 1: for(i = 1; i < n; i++) if(Miller_Rabin(i)) ans += i; break; case 2: for(auto x : prime) if(x < n) ans += x; else break; break; } cout< <
转载于:https://www.cnblogs.com/Saurus/p/6017219.html