求解素数的筛选法

题目：请编写代码找出1-120之间的素数。

关于求一个范围内的素数，有两种方法，一个是试除法，一个是筛选法。

本文章主要介绍筛选法。

筛选法是将不是素数的数全部去除，然后得到余下的数来达到目的。

我的思路是：

1. 将1-120存储到数组prime[]中，并且使数组下标和数据内容一致。例如：prime[i]等于i。该数组中的第一个元素，即prime[0]则等于0。
2. 假设一个数组is_prime[],is_prime[i]存储prime[i]是否是素数 ，是则存储1， 不是则存储-1。注：is_prime[0]记为-1。
3. 判断prime[i]是否是素数。

判断方法：

•    首先1不是质数，所以is_prime[1]赋值为-1；
•       接着2是公认最小的质数，所以is_prime[2]赋值为1，再把所有2的倍数标记起来，即is_prime[j]赋值为-1，这里的j代表着所有2的倍数；
•        跳过is_prime[i]等于-1时的prime[i]。
•        然后接下来遇到的第一数不会是被标记过的数，即不是2的倍数，所以它必然只可能被1和他自身整除，为素数，而2后面第一个没有被标记的数是3，所以要标记素数3，再把所有3的倍数也标记起来；
•        按照上面的判断方法，将剩下的数不断地标记起来...
• 当is_prime[i]等于1时，prime[i]即为素数.

代码：

代码语言：javascript复制

//i=1,自动去除掉  i=2 i的倍数去除掉

#include<stdio.h>

#define Num 150

int main()
{
	int i = 0,j=0;
	//数组存储1-120
	int prime[Num] = { 0 };
	//is_prime[i]存储prime[i]是否是素数 是->1 不是->-1
	int is_prime[Num] = {0};
	//1忽略
	is_prime[0] = -1;
	is_prime[1] = -1;//prime[1]==1
	//使prime[i]==i
	for (i=1;i<=120;i  )
	{
		prime[i] = i;
	}
	for (i = 2;i <= 120;i  )
	{
		if (is_prime[i] != -1)
		{
			is_prime[i] = 1;
			for (j = i * i;j <= 120;j  = i)
			{
				//满足倍数关系			
				is_prime[j] = -1;

			}
		}
	}
	for (i = 1;i <= 120;i  )
	{
		if (is_prime[i] == 1)
		{
			printf("%d  ", prime[i]);
		}
	}
	return 0;
}

这篇博客如果对你有帮助，给博主一个免费的点赞以示鼓励，欢迎各位