数组筛选法 （C语言代码）

解题思路:

    题目要求使用筛选法完成算法，筛选法的具体思路：

    1)遍历1~n的自然数组

    2)判断当前位arr[0] = 1，1不是素数，跳过

    3)判断arr[1] = 2，2是素数，保留并打印，并且后面1~n位依次判断是否能被2整除，能被整除则置1

    4)继续判断下一位是否为1，非1则判断是否为素数，是素数则后面能被整除的的数置1

    ......

参考代码:

#include <stdio.h>
int main()
{
	int n, i, j;
	int arr[1000];
	scanf("%d", &n);
	for (i = 0; i < n; i++)//遍历数组
		arr[i] = i + 1;
	for (i = 0; i < n; i++)
	{
		if (arr[i] != 1)//跳过数组中所有1的位置
		{
			j = i;
			while (arr[i] % j != 0)
				j--;//如果arr[i]是素数，则会一直判断到j=1为止
			if (j == 1)
			{
				for (j = i + 1; j < n; j++)
				{
					if (arr[j] % arr[i] == 0)
						arr[j] = 1;//能被arr[i]整除的置1
				}
				printf("%d\n", arr[i]);
			}
		}
	}
	return 0;
}