素数筛

拼搏现实的明天。 2023-10-06 16:35 46阅读 0赞

#### 目录 ####

*   *  题目
     *  思路1
     *  思路2
     *  思路3

### 题目 ###

给定一个正整数n(2≤n≤10000)，先输出2~n之间的素数个数，换行后输出所有的素数。  
输入：  
9  
输出：  
4  
2 3 5 7

### 思路1 ###

先写一个判断素数的方法，然后遍历2~n，逐一进行判断。

#include <iostream>
    #include <math.h>
    #define MaxSize 10000
    
    using namespace std;
    
    //判断一个数是否为素数，是素数返回true，否则返回false 
    bool isPrime(int num){
        
    	if (num == 2){
        
    		return true;
    	}
    	for (int i = 2; i<= sqrt(num); i++){
        
    		if (num%i == 0)
    			return false;
    	}
    	return true;
    }
    
    void displayPrime(){
        
    	int n,cnt=0;
    	int prime[MaxSize]={
        0};
    	cin>>n;
    	for (int i=2;i<=n;i++){
        
    		if(isPrime(i)){
        
    			prime[cnt++]=i;;
    		}
    	}
    	cout<<cnt<<endl;
    	for(int i=0;i<cnt;i++){
        
    		cout<<prime[i]<<" ";
    	}
    	cout<<endl;
    }

### 思路2 ###

埃拉托斯特尼筛法(Sieve of Eratosthenes)，其思想是把不大于根号n的所有素数的倍数剔除，那么剩下的就是素数。

#include <iostream>
    #include <math.h>
    #define MaxSize 10000
    
    using namespace std;
    
    //埃拉托斯特尼筛法
    void Eratosthenes(){
        
    	int n,cnt=0;
    	int prime[MaxSize]={
        0};
    	int check[MaxSize]={
        0};
    	cin>>n;
    	for(int i=2; i<=n; i++)
    	{
        
    		if(check[i] == 0){
        
    			prime[cnt++] = i;
    		}
    		for(int j = i + i; j <= n; j += i){
        
    			//将i的倍数全部标记为非素数
    			check[j] = 1;      
    		}
    	}
    	cout<<cnt<<endl;
    	for(int i=0;i<cnt;i++){
        
    		cout<<prime[i]<<" ";
    	}
    	cout<<endl;
    }

### 思路3 ###

欧拉筛法。在埃拉托斯特尼筛法的基础上，让每个合数只被它的最小质因子筛选一次，这样可以达到不重复的目的。

#include <iostream>
    #include <math.h>
    #define MaxSize 10000
    
    using namespace std;
    
    //欧拉筛法
    void Euler(){
        
    	int n,cnt=0;
    	int prime[MaxSize]={
        0};
    	int check[MaxSize]={
        0};
    	cin>>n;
    	for (int i = 2; i<=n; i++){
        
    		if (check[i] == 0){
        
    			prime[cnt++] = i;
    		}
    		for (int j = 0;j <cnt; j++){
        
    			//若超过n的值，则退出循环
    			if (i*prime[j] > n){
        
    				break;		
    			}
    			//将数组prime里面纪录的素数，升序来当作要标记非素数的最小因子
    			check[i*prime[j]] = 1;			
    			if(i%prime[j] == 0){
        
    				break;
    			}
    		}
    	}
    	cout<<cnt<<endl;
    	for(int i=0;i<cnt;i++){
        
    		cout<<prime[i]<<" ";
    	}
    	cout<<endl;
    }