C语言 素数筛

素数筛

描述

素数（质数）：除了1和它本身之外不能被其他数整除的数。

合数：除了1和它本身之外能被其他数整除的数。

1既不是素数也不是合数。

给你一个区间 l r，请你输出 l r 中所有的素数

输入

输入两个数l和r

1 ≤ l < r ≤ 1000000

输出

输出l r之间的所有素数

简单的循环加判断方法;

#include 
int main()
{
	int l,r;
	scanf("%d %d",&l,&r);
	int k=1;
	for(int i=l;i<=r;i++){
		for(int j=2;j 
但是容易运行超时，这里我们为了减少循环，节省时间，可以在循环上面看。
 
我们知道，素数除了2以外都是奇数，所以我们可以先把偶数去掉，只循环奇数来判断素数
 
#include 
int main()
{
	int l,r;
	scanf("%d %d",&l,&r);
	int ret = 1;
	int i;
	for(int x=l;x<=r;x++){
		if(x==1||(x%2==0&&x!=2))
		ret = 0;
		for(i=3;i 
还有我们可以认为，因为去除了偶数，根据数学知识可以想到，判断循环条件只要满足i<√x即可。因此做点小小的改动：
 
​
#include 
#include 
int main()
{
	int l,r;
	scanf("%d %d",&l,&r);
	int ret = 1;
	int i;
	for(int x=l;x<=r;x++){
		if(x==1||(x%2==0&&x!=2))
		ret = 0;
		for(i=3;i<=sqrt(x);i+=2){
			if(x%i==0){
				ret = 0;
				break;
			}
		}
		if(ret == 1){
			printf("%d ",x);
		} else{
			ret = 1;
		}
}
	return 0;
}

​