题目描述
给你两个数,求两个数之间素数的个数。
输入:
输入有两个数,一个a,一个b,求a到b之间素数的个数
其中1<=a<=b<=1e12
其中b-a<=1e7
输出:
一个数,表示a-b之间素数的个数。
样例输入:
1 10
样例输出:
4
题目描述
给你两个数,求两个数之间素数的个数。
输入:
输入有两个数,一个a,一个b,求a到b之间素数的个数
其中1<=a<=b<=1e12
其中b-a<=1e7
输出:
一个数,表示a-b之间素数的个数。
样例输入:
1 10
样例输出:
4
#include <stdio.h>
#include<math.h>
bool isPrime(int num)
{
int i = 2;
if(num <= 1)
{
return false;
}
int sqrNum = sqrt(num);
for(i = 2; i <= sqrNum; i++)
{
if(num % i == 0)
{
return false;
}
}
return true;
}
int getPrimeCount(int a, int b)
{
int sum = 0;
if(a > b)
{
return sum;
}
for(; a <= b; a++)
{
if(isPrime(a))
{
sum++;
}
}
return sum;
}
int main()
{
int a, b;
printf("input two num:\n");
scanf("%d %d", &a, &b);
printf("sum is %d\n", getPrimeCount(a, b));
}
两个函数,分别是判断是否为素数,和获取两个数之间素数的个数。为了快速得出是否为素数,这里只判断小于该数的开方的数能否被除尽。