素数的几种求法

柔光的暖阳◎ 2023-10-11 14:46 15阅读 0赞

## 素数筛法 ##

素数筛法埃氏和线式的思想差不太多，都是采用事先打表的思想进行初始化，以供后面使用。

#### MaxFactor埃氏筛法 ####

bool is_pri[N+5];
    void prime(){
        
    	memset(is_pri, true, sizeof(is_pri));	
    	is_pri[0] = false;//由于输入情况有可能小于2
    	is_pri[1] = false;
    	
    	for(int i = 2; i <= N; i ++){
        
    		if(is_pri[i]){
        
    			for(int j = 2*i; j <= N; j+=i)
    				is_pri[j] = false;
    		}
    	}
    }

#### MaxFactor线式筛法 ####

bool is_pri[N+10];
    void prime(){
        
    	memset(is_pri, true, sizeof(is_pri));
    	is_pri[0] = false; 
    	is_pri[1] = false;
    	
    	for(int i = 2; i <= N; i ++){
        
    		if(is_pri[i]){
        
    			for(int j = i*i; j <= N; j += i)
    				is_pri[j] = 1;
    		}	
    	}
    }

### 示例：求200以内素数 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define N 200
    using namespace std; 
    
    bool is_pri[N+5];
    void prime(){
        
    	memset(is_pri, true, sizeof(is_pri));	
    	is_pri[0] = false;//由于输入情况有可能小于2
    	is_pri[1] = false;
    
    	for(int i = 2; i <= N; i ++){
        
    		if(is_pri[i]){
        
    			for(int j = 2*i; j <= N; j+=i)
    				is_pri[j] = false;
    		}
    	}
    }
    
    int main(){
        
    	prime();
    	for(int i = 1 ; i <= N; i ++){
        
    		if(is_pri[i]){
        
    			printf("%d%c", i, i==N-1?'\n':' ');	
    		} 
    	}
    	return 0;
    }

--------------------

## 正常求法 ##

int m, pri[max];
    void prime(int n){
        
    	int i, j;
    	memset(pri, 0, sizeof(pri));
    	for( i = 2; i <= n; i ++){
        
    		for( j = 2; j <= sqrt(i); j ++){
        
    			if(i%j == 0)
    				break;
    		}
    		if(j > sqrt(i))
    			pri[m++] = i;
    	}
    }

注：max 是宏定义

int m, pri[max];
    void prime(int n){
        
    	int i, j;
    	memset(pri, 0, sizeof(pri));
    	for( i = 2; i <= n; i ++){
        
    		for( j = 2; j <= i/2; j ++){
        
    			if(i%j == 0)
    				break;
    		}
    		if(j > i/2)
    			pri[m++] = i;
    	}
    }