C语言 素数筛_请问有多少组整数对 l, r 满足: 　　1. l 和 r 都介于 0 (含)到 100 (含)之间

素数筛

描述

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

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

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

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

输入

输入两个数l和r

1 ≤ l < r ≤ 1000000

输出

输出l r之间的所有素数

简单的循环加判断方法;

#include <stdio.h>
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<i;j++){
			if(i%j==0){
				k=0;
				break;
			}
		}
		if(k==1){
			printf("%d ",i);
		}else{
			k=1;
		}
	}
	return 0;
}

但是容易运行超时，这里我们为了减少循环，节省时间，可以在循环上面看。

我们知道，素数除了2以外都是奇数，所以我们可以先把偶数去掉，只循环奇数来判断素数

#include <stdio.h>
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<x;i+=2){
			if(x%i==0){
				ret = 0;
				break;
			}
		}
		if(ret == 1){
			printf("%d ",x);
		} else{
			ret = 1;
		}
}
	return 0;
}

还有我们可以认为，因为去除了偶数，根据数学知识可以想到，判断循环条件只要满足i<√x即可。因此做点小小的改动：

​
#include <stdio.h>
#include <math.h>
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;
}
 
​