A27728. 平方因子多多有一些正整数n,n+1,n+2,...m，如 n=3,m=9 时，多多有3,4,5,6,7,8,9 七个数。 多多不喜欢平方因子，如 4,9,16,25 都是平方因子，而1不算平方因子，多多想知道他的这些数当中有多少数中不包含平方因子？在 3～9 这些数中包含平方因子的数有4,8,9 三个数，不包含平方因子的数是 3,5,6,7 四个数。
填空题
中等
知识点
题目描述
平方因子
多多有一些正整数n,n+1,n+2,...m，如 n=3,m=9 时，多多有3,4,5,6,7,8,9 七个数。
多多不喜欢平方因子，如 4,9,16,25 都是平方因子，而1不算平方因子，多多想知道他的这些数当中有多少数中不包含平方因子？在 3～9 这些数中包含平方因子的数有4,8,9 三个数，不包含平方因子的数是 3,5,6,7 四个数。
输入格式
输入一行，两个数n,m（1<=n,m<=1000000）
输出格式
输出一个整数表示答案。
输入/输出例子1
输入
1 10
输出
7
参考答案
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000005],p[1000005],cntp;
int main()
{
for(int i=2;i*i<=1000000;i++)
{
p[++cntp]=i*i;
}
for(int i=1;i<=cntp;i++)
for(int j=p[i];j<=1000000;j+=p[i])
a[j]=1;
cin >> n >> m;
int ans = 0;
for (int i = n; i <= m; i++)
if (a[i]==0) ans++;
cout << ans << endl;
return 0;
}
上一题
下一题