素数学习小结

﹏ヽ暗。殇╰゛Y 2022-01-14 05:43 258阅读 0赞

### 素数学习小结 ###

*  判断一个数是否是素数
 *  埃拉托斯特尼筛法在O(nloglogn)内筛选素数
 *   *  优化
 *  欧拉筛法在O(n)内筛选素数

# 判断一个数是否是素数 #

bool prime(int n){ 
        if(n<=1)return false;
        for(int j=2;j*j<=n;j++){ 
            if(n%j==0){ 
                printf("%d\n",j);
                return false;
            }
        }
        return true;
    }

# 埃拉托斯特尼筛法在O(nloglogn)内筛选素数 #

#include <bits/stdc++.h>
    using  namespace std;
    const  int MAXN = 100;
    
    bool number[MAXN]={ false};
    
    void EratosthenesPrime(){ 
        for(int i=2;i<MAXN;i++){ 
            if(!number[i]){ 
                for(int j=2*i;j<MAXN;j+=i)number[j]=true;
            }
        }
    }
    
    int main(){ 
        printf("%d以内的素数：\n",MAXN);
        EratosthenesPrime();
       for(int i=2;i<MAXN;i++){ 
           if(!number[i])printf("%d ",i);
       }
        return 0;
    }

## 优化 ##

#include <bits/stdc++.h>
    using  namespace std;
    const  int MAXN = 100;
    
    bool number[MAXN]={ false};
    
    void EratosthenesPrime(){ 
        for(int i=2;i*i<MAXN;i++){ 
            if(!number[i]){ 
                for(int j=i*i;j<MAXN;j+=i)number[j]=true;
            }
        }
    }
    
    int main(){ 
        printf("%d以内的素数：\n",MAXN);
        EratosthenesPrime();
       for(int i=2;i<MAXN;i++){ 
           if(!number[i])printf("%d ",i);
       }
        return 0;
    }

# 欧拉筛法在O(n)内筛选素数 #

#include <bits/stdc++.h>
    using  namespace std;
    const  int MAXN = 100;
    
    bool vis[MAXN];
    int  prime[MAXN],index=0;
    void EuerPrime(){ 
        for (int i=2; i<MAXN; i++)
        { 
            if (!vis[i]) prime[index++]=i;
            for(int j=0; prime[j]*i<MAXN; j++)
            { 
                vis[prime[j]*i]=1;
                if(i%prime[j]==0)break;
            }
        }
    }
    
    int main(){ 
        printf("%d以内的素数：\n",MAXN);
        EuerPrime();
        for(int i=0;i<index;i++)printf("%d ",prime[i]);
        return 0;
    }