问题描述
小蓝非常热爱数学,一天老师给小蓝出了一道数学题,想锻炼锻炼小蓝的思维能力。题目是这样的:给定两个数 a 和 b,在 a 到 b(包括 a 和 b)之间所有数的平方当中,试问有几个数能够表示为 x×y 的形式,其中 x 和 y 是质数。你能帮助小蓝一起来解决这个问题吗?
输入格式
第一行两个正整数 a,b,含义同题目所示。
输出格式
输出共一行,输出一个整数,代表那些能够表示为题目描述的形式的平方数的数量。
样例输入
1 5
样例输出
3
说明
样例中,在1到5之间产生的平方数为:1、4、9、16和25。其中只有4、9和25是满足题目要求的平方数,所以答案为3。
评测数据规模
对于所有评测数据,1≤a<b≤105。
思路:
只要找a~b之间的素数即可
代码如下:
#include <iostream>
using namespace std;
int a,b;
bool is_pirme(int x)
{if(x < 2)return false;if(x == 2)return true;for(int i = 2 ; i * i <= x ; i++){if(x % i == 0)return false;}return true;
}
int main()
{int cnt = 0;cin >> a >> b;for(int i = a ; i <= b ; i++){if(is_pirme(i)){cnt++;}}cout << cnt;return 0;
}