素数有关基本算法

该文章包含模块为判断素数，分解质因数，筛素数三大模块

• 判断素数

• ---

  我们最容易想到的素数判断就是试除法，就是枚举从2到n-1中所有的数，尝试从其中找到n的因数，找到了就是合数，反之则为素数，实践复杂度为O(n)。
• 然而我们很容易发现该方法重复了许多无用的步骤，比如很明显的n-1就很难是n的因数，我们可以尝试从其中找出那些重复的数。
• 我们想到，如果一个数是合数，那么因数一定是成对出现的，并且似乎是“均匀”地分布在根号n两侧，那么我们就可以大大减少重复的次数

•  1 bool is_prime(int n){
   2     
   3     if(n<2)return false;
   4     
   5     for(int i=2;i<=n/i;i++){
   6         if(n%i==0)return false;
   7     }
   8     
   9     return true;
  10 }

   

• 分解质因数

• ---

  如果我们想找到一个合数的质因数及其幂，那么我们只需要简单的利用以下程序

•  1 void prime(int n){
   2     
   3     for(int i=2;i<=n/i;i++){
   4         
   5         if(n%i==0){
   6             int s=0;
   7             while(n%i==0){
   8                 n/=i;
   9                 s++;
  10             }
  11             printf("%d %d\n",i,s);
  12         }
  13         
  14     }
  15     
  16     if(n>1)printf("%d 1\n",n);
  17     puts("");
  18 }

  比较好理解，不做过多讲解

• 筛素数

• ---

  现在试想我们想从1-n中将所有素数筛选出来并找到其个数，我们不可能对于每个数都用一遍暴力判断和优化判断，即使是优化判断的实践复杂度也是可想而知的高，这里，我们可以不妨考虑将所有的合数筛出来，那么剩下的数就是素数。
• 下面分为埃氏筛法和欧式筛法，其中在n的量级较大时(>=1e6)，后者比前者快得多，虽然两者耗时都不长。
• 埃氏筛法————
• 基本思路是利用合数可以分解为质因数之积的原理，我们利用已经筛出的素数筛掉合数，时间复杂度为nln(n)

•  1 void find_prime(int n){
   2     
   3     if(n<2)return;
   4     
   5     for(int i=2;i<=n;i++){
   6         if(!st[i]){
   7             cnt++;
   8             for(int j=i+i;j<=n;j+=i){
   9                 st[j]=true;
  10             }
  11         }
  12     }
  13 }

   

• 欧式筛法————
• 我们从上面的埃氏筛法可以看到，尽管上面的筛法看起来已经优化了不少，我们还是可以从中看到其中有许多合数被重复筛掉，欧式筛法恰恰可以避免这种情况，以至于我们的时间是线性的

•  1 void find_prime(int n){
   2     
   3     if(n<2)return;
   4     
   5     for(int i=2;i<=n;i++){
   6         
   7         if(!st[i])prime[cnt++]=i;
   8         
   9         for(int j=0;prime[j]<=n/i;j++){
  10             st[prime[j]*i]=true;
  11             if(i%prime[j]==0)break;
  12         }
  13     }
  14 }