【16届蓝桥杯寒假刷题营】第1期DAY5
问题描述
小蓝非常热爱数学，一天老师给小蓝出了一道数学题，想锻炼锻炼小蓝的思维能力。题目是这样的：给定两个数 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;
}