题解 | #找出区间内所有素数#

#include<stdio.h>
#include<math.h>
#include<string.h>

bool Judge(int n){
    if(n<=1) return false;//负数和0、1都是非素数 
    int max = sqrt((float)n);//算到sqrt(n)即可 
    for(int i=2;i<=max;i++)
        if(n%i==0) return false;
    return true;
}

void Example6_8(){//例题6.8 北航  找出所有素数
	//反向思考、打表法
	//每确定一个素数，就将其倍数都标记为非素数

	int n;
	int flag[10001];
	for(int i=0;i<=10001;i++) flag[i] = 0;
	
	flag[0] = -1;
	flag[1] = -1;
	for(int i=2;i<=10000;i++){
		if(flag[i]!=0) continue;//已经打表了 
		if(Judge(i)){
			flag[i] = 1;//自己是素数 
			for(int j=2;j*i<=10000;j++){
				flag[j*i] = -1;//素数的倍数是合数 
			}
		} else {
			flag[i] = -1;
		}
	}
	
	//打表之后，每次查表即可 
	while(scanf("%d",&n)!=EOF){
		int counter = 0;
		for(int i=2;i<n;i++){
			if(flag[i]!=1) continue;
			if(i%10!=1) continue;
			printf("%d ",i);
			counter++;
		}
		if(counter==0) printf("-1\n");
	} 
} 

int main(){
    
	Example6_8();
    
    return 0;
}