1098 素数个数

Description
给定两个非负整数a，b，其中0<= a,b<=1,000,000，请计算这两个数之间有多少个素数。

输入

第一行是一个整数K（1<=K<=1000），表示有多少个样例，每个样例占一行，是两个整数a和b，每个整数之间用一个空格隔开。

输出

每行输出一个样例的结果。

Sample Input
2
2 3
17 19

Sample Output
2
2

Source
ericxie

#include <stdio.h>
#include <math.h>
#include <string.h>
#define maxn 1000005
int n[maxn];
int main()
{
	memset(n,1,sizeof(n));//n数组赋值为1
	n[0]=!n[0];//0和1都不是素数
	n[1]=!n[1];
	for(int i=4;i<=1000000;i++)
	{
		for(int j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)//能够被整除，那就不是素数
			{
				n[i]=!n[i];
				break;//结束该循环
			}
		}
	}
	int k;
	scanf("%d",&k);
	while(k--)
	{
		int a,b,t;
		scanf("%d%d",&a,&b);
		if(a>b)//如果a大于b，那就需要交换
		{
			t=a;
			a=b;
			b=t;
		}
		int count=0;//计数器
		for(int i=a;i<=b;i++)
		{
			if(n[i])//如果是素数，计数器增加1
			{
				count++;
			}
		}
		printf("%d\n",count);//输出
	}
	return 0;
}

写于2021年8月25日19：03分