两种方法求小于n的所有质数

以下介绍常用方法和筛选法两种

常用方法

/*
通用方法求小于n的所有质数 
*/ 
#include <stdio.h>
#include <math.h>
#define MAX 1000

int main(){
	int n;
	int pi = 0,p[MAX];
	scanf("%d",&n);
	for(int k = 2;k<n;k++){
		int i;
		for(i = 2;i<=sqrt(k);i++){
			if(k % i == 0){
				break;
			}
		}
		if(i > sqrt(k)){
			p[pi++] = k;
			printf("%d ",k);
		}
	}
	return 0;
} 

筛法

/*
筛法求小于n的所有质数 
*/
#include <stdio.h>
#define MAX 1000

int main(){
	int n;
	int prime[MAX];
	scanf("%d",&n);
	for(int i = 2;i<=n;i++)
		prime[i] = i;
	for(int i = 2;i<=n;i++){
		if(prime[i] != 0){
			for(int j = i+i;j<=n;j+=i){
				prime[j] = 0;
			}
		}
	}
	
	for(int i = 2;i<n;i++){
		if(prime[i] != 0)
			printf("%d ",prime[i]);
	}
	return 0;
}