用筛选法求100之内的素数——C语言

1 筛选法

首先必须解释一下什么是筛选法！筛选法其实是把我们不需要的数给筛出掉！
本题具体做法如下：

1. 先把N个自然数按次序排列起来，本题中直接采用数据即可；
2. 1不是素数（质数），也不是合数，筛去；
3. 第二个数2是素数，保留下来，把2后面所有能被2整除的数都筛去，因为这些数肯定不是素数了；
4. 2后面第一个没筛去的数是3，3保留，再把3后面所有能被3整除的数都筛去；
5. 3后面第一个没筛去的数是5，把5留下，再把5后面所有能被5整除的数都筛去；
6. 一直循环，直到某个数后面没有数剩下了为止。那么留下的就全部都是N以内的质数了。

本题中的筛去可直接设定为0，为0的就代表筛去了。

2 实现代码

#include <stdio.h>

int main(){
	int x[100],i,j;  // 定义一个数组
	for(i=0;i<100;i++)
		x[i] = i+1;  // 给数组每一个赋值，其实就是100以内的所有数了
	x[0] = 0;  // 第一位，也就是1，不是素数也不是合数，直接筛掉
	for(i=1;i<100;i++){  // 从第二位开始循环
		if(x[i] != 0){  // 判断本位是不是已经是0了，如果是，就直接下一位 
			for(j=i+1;j<100;j++){  // 从i+1位开始，筛除掉后面能够被x[i] 整数的所有数 
				if(x[j] != 0){  // 判断 x[j] 是不是已经是0了， 如果是，就直接下一位 
				 	if(x[j]%x[i] == 0){
				 		x[j] = 0;
					}
				}
			}
		} 	
	}
	for(i=1;i<100;i++){
		if(x[i] != 0){
			printf("%d\n", x[i]);
		}
	}
	return 0;
}