ACM数论之旅1---素数（万事开头难（>

前言：好多学ACM的人都在问我数论的知识（其实我本人分不清数学和数论有什么区别，反正以后有关数学的知识我都扔进数论分类里面好了）

于是我就准备写一个长篇集，把我知道的数论知识和ACM模板都发上来（而且一旦模板有更新，我就直接在博客上改了，所以记得常来看看（。・ω・））

废话说完了，直接进入正题ヾ(=^▽^=)ノ

素数，又叫质数，定义是除了1和它本身以外不再有其他的因数

我们通过这个定义，可以写如下程序判断一个数是不是质数

 bool prime(int x){//判断x是不是质数，是返回true，不是返回false

     if(x <= ) return false;

     for(int i = ; i < x; i ++){

         if(x % i == ) return false;

     }

     return true;

 }

这个程序的时间复杂度是O(n)，有没有更快的方法，当然

看这个

 bool prime(int x){//判断x是不是质数，是返回true，不是返回false

     if(x <= ) return false;

     for(int i = ; i <= sqrt(x + 0.5); i ++){//0.5是防止根号的精度误差

         if(x % i == ) return false;

     }

     return true;

 }

 //另一种方法，不需要根号

 bool prime(int x){//判断x是不是质数，是返回true，不是返回false

     if(x <= ) return false;

     for(int i = ; i * i <= x; i ++){//用乘法避免根号的精度误差

         if(x % i == ) return false;

     }

     return true;

 }

 //根据题目不同，如果i*i会爆int，记得开longlong

这个复杂度是O(√n),速度快多了（＃°Д°）

根据题目不同，有可能你需要先预处理出1~N这N个数是否是素数

如果用刚刚的方法，复杂度就是O(n√n)

 #include<cstdio>

 const int N =  + ;

 bool prime[N];

 bool is_prime(int x){

     if(x <= ) return false;

     for(int i = ; i * i <= x; i ++){

         if(x % i == ) return false;

     }

     return true;

 }

 void init(){

     for(int i = ; i < N; i ++){

         prime[i] = is_prime(i);

     }

 }

 int main(){

     init();

 }

如果n大一点，就太慢了(｡･ω･)ﾉﾞ

介绍一种新方法，埃筛

埃筛--------------埃拉托斯特尼筛法，或者叫埃氏筛法

原理：如果找到一个质数，那么这个质数的倍数都不是质数

比如2是质数，那么4,6,8,10,12...都不是质数

然后看3是质数，那么6,9,12,15,18,21...都不是质数

然后看4，4已经被2标记为合数了，所以跳过

然后看5......这样一直筛下去

 #include<cstdio>

 const int N =  + ;

 bool prime[N];

 void init(){

     for(int i = ; i < N; i ++) prime[i] = true;//先全部初始化为质数

     for(int i = ; i < N; i ++){

         if(prime[i]){//如果i是质数

             for(int j = *i; j < N; j += i){//从i的两倍开始的所有倍数

                 prime[j] = false;

             }

         }

     }

 }

 int main(){

     init();

 }

因为一些数字，比如6既被2的for循环经过又被3的for循环经过，所以复杂度不是O(n)

这个复杂度经过专业人士检验，复杂度O(nloglogn)（学过高数的小朋友可以自己证明≖‿≖✧当然也可以去百度）

知道原理后，我们再稍微优化一下就更快了

 #include<cstdio>

 const int N =  + ;

 bool prime[N];

 void init(){

     for(int i = ; i < N; i ++) prime[i] = true;

     for(int i = ; i*i < N; i ++){//判断改成i*i<N

         if(prime[i]){

             for(int j = i*i; j < N; j += i){//从i*i开始就可以了

                 prime[j] = false;

             }

         }

     }

 }

 int main(){

     init();

 }

好戏都是要留到最后的≖‿≖✧确实还有O(n)的做法

这个算法名字叫线筛

 #include<cstdio>

 const int N =  + ;

 bool prime[N];//prime[i]表示i是不是质数

 int p[N], tot;//p[N]用来存质数

 void init(){

     for(int i = ; i < N; i ++) prime[i] = true;//初始化为质数

     for(int i = ; i < N; i++){

         if(prime[i]) p[tot ++] = i;//把质数存起来

         for(int j = ; j < tot && i * p[j] < N; j++){

             prime[i * p[j]] = false;

             if(i % p[j] == ) break;//保证每个合数被它最小的质因数筛去

         }

     }

 }

 int main(){

     init();

 }

这个方法可以保证每个合数都被它最小的质因数筛去

所以一个数只会经过一次

时间复杂度为O(n)

其实loglogn非常小，把埃筛看成线性也无妨，毕竟它比线筛好写

基于埃筛的原理，我们可以用它干很多事

比如预处理每个数的所有质因数

 #include<cstdio>

 #include<vector>

 using namespace std;

 const int N =  + ;

 vector<int > prime_factor[N];

 void init(){

     for(int i = ; i < N; i ++){

         if(prime_factor[i].size() == ){//如果i是质数

             for(int j = i; j < N; j += i){

                 prime_factor[j].push_back(i);

             }

         }

     }

 }

 int main(){

     init();

 }

比如预处理每个数的所有因数

 #include<cstdio>

 #include<vector>

 using namespace std;

 const int N =  + ;

 vector<int > factor[N];

 void init(){

     for(int i = ; i < N; i ++){

         for(int j = i; j < N; j += i){

             factor[j].push_back(i);

         }

     }

 }

 int main(){

     init();

 }

比如预处理每个数的质因数分解

 #include<cstdio>

 #include<vector>

 using namespace std;

 const int N =  + ;

 vector<int > prime_factor[N];

 void init(){

     int temp;

     for(int i = ; i < N; i ++){

         if(prime_factor[i].size() == ){

             for(int j = i; j < N; j += i){

                 temp = j;

                 while(temp % i == ){

                     prime_factor[j].push_back(i);

                     temp /= i;

                 }

             }

         }

     }

 }

 int main(){

     init();

 }

世界之大无奇不有(。-`ω´-)数论是个可怕的东西

巴特西

ACM数论之旅1---素数（万事开头难（>_<））

最新文章

热门文章