Acwing 算法数学知识模板——质数-灵析社区

Acwing 算法数学知识模板——质数

数学模块第一章打卡题，质数模块，该部分介四种方法来解决三道关于质数的题目，分别是质数判定、分解质因数以及筛质数，感兴趣的可以看看。

质数判定

试除法判定质数 —— 模板题 AcWing 866. 试除法判定质数

时间复杂度 O(sqrt(n))

 public static boolean is_prime(int n) {
     if(n < 2){
         return false;
      }
      for(int i = 2;i <= n / i;i++){
         if(n % i == 0){
            return false;
          }
       }
      return true;
 }

试除法分解质因数 —— 模板题 AcWing 867. 分解质因数

时间复杂度 O(log n)- O(sqrt(n))

 void divide(int x){
     for(int i = 2; i <= x/ i; i++){
         if(x % i== 0){
             int s = 0;
             while(x % i == 0){
                 x /= i;
                 s++;
             }
             cout << i << ' ' << s<<endl;
         }
     }
     if(x > 1){
         cout << x << ' ' << 1 <<endl;
     }
     cout<<endl;
 }

朴素筛法求素数 (埃氏筛)—— 模板题 AcWing 868. 筛质数

时间复杂度O(nloglogn)

 const int N = 1000010;
 int primes[N], cnt;     // primes[]存储所有素数
 bool st[N];         // st[x]存储x是否被筛掉
 
 
 void get_primes(int n){
    for(int i = 2;i <= n; i++){
        if(st[i]) continue;
        primes[cnt++] = i;
        for(int j = i + i; j <= n;j+=i){
            st[j] = true;
        }
    }
 }

线性筛法求素数 —— 模板题 AcWing 868. 筛质数

时间复杂度 O(lnn)

 const int N = 1000010;
 int primes[N], cnt;     // primes[]存储所有素数
 bool st[N];         // st[x]存储x是否被筛掉
 
 
 void get_primes(int n){
     for(int i = 2; i<= n;i++){
         if(!st[i]){
             primes[cnt++]=i;
         }
         for(int j = 0; primes[j] <= n /i; j++){
             st[primes[j] * i] = true;
             if(i % primes[j] == 0){
                 break;
             }
         }
     }
 }

阅读量：1581

点赞量：0

收藏量:0