ZCMU--5104: SuShu?(C语言)

HH likes math very much. Today he found some numbers that are special. These special
numbers are defined as "numbers that can be divisible by less than 3 positive integers." Now HH
wants to ask you how many special numbers there are in the interval [L,R].

The first line contains two integers L,R — the interval. ( 0 <= L <= R <= 100000 )

Output the number of special numbers in the interval [L,R].

3 6

2

Only 3, 5 in 3, 4, 5, 6 are special numbers

解析：题目让我们求出给定区间内能被小于3个数整除的数，我们知道一个数肯定能被1和它本身整除，因此几乎就是让我们判断区间有多少素数，为什么是几乎呢，因为这道题中1也满足条件，是特殊数，0不是特殊数，其他跟素数无异。

#include 
int su(int n){
	int i,shi=1; //shi表示是否为特殊数 
	if(n==0) shi=0;
	if(n==1) shi=1;		//1是特殊数 
	for(i=2;i*i<=n;i++){	//到i*i<=n即可，跟素数相同 
		if(n%i==0){
			shi=0;
			break;
		}
	}
	return shi;
}
int main()
{
	int a,b,i,cnt=0;
	scanf("%d%d",&a,&b);
	for(i=a;i<=b;i++){
		if(su(i)==1) cnt++; //计数 
	}
	printf("%dn",cnt);
	return 0;
}