A25283. factorization问题描述Adleman非常喜欢数学，最近他遇到了一个棘手的问题：对于一个正整数A，Adleman发现一些自然数的质因子分解式中没有大于A的因子，这样的自然数非常的特殊。Adleman想知道对于给定的正整数A，一个区间[N, N+M]内所有满足上述条件的自然数的个数。输入说明第一行：3个用空格分开的整数N、M、A。输出说明第一行：一个整数，表示对于给定的正整数A，区间[N…
填空题
较易
知识点
题目描述
factorization
问题描述
Adleman非常喜欢数学，最近他遇到了一个棘手的问题：
对于一个正整数A，Adleman发现一些自然数的质因子分解式中没有大于A的因子，这样的自然数非常的特殊。Adleman想知道对于给定的正整数A，一个区间[N, N+M]内所有满足上述条件的自然数的个数。
输入说明
第一行：3个用空格分开的整数N、M、A。
输出说明
第一行：一个整数，表示对于给定的正整数A，区间[N, N+M]内特殊自然数的个数。
样例输入
30 10 5样例输出
4样例解释
[30, 40]之间的数质因子分解式如下：
30=2*3*5
31=1*31
32=2*2*2*2*2
33=3*11
34=2*17
35=5*7
36=2*2*3*3
37=1*37
38=2*19
39=3*13
40=2*2*2*5其中30、32、36、40的质因子分解式中没有大于5的因子，所以一共有4个。
数据范围
50%的数据满足：1≤N,M,A≤5000
100%的数据满足：1≤N,M,A≤50,000
参考答案
#include <iostream>
using namespace std;
int main()
{
int n,m,a;
cin>>n>>m>>a;
m += n;
int ans=0;
for(int i=n; i<=m; i++)
{
int temp=i;
for(int j=2; j*j<=temp && j<=a; j++) // 枚举到sqrt(i)，否则会超时
{
while(temp%j==0)
temp /= j;
}
if(temp<=a)
ans++;
}
cout<<ans<<endl;
return 0;
}答案解析
从数学可知，一个正整数的质因子分解式是唯一的。
这里，我们可以利用“素数筛法”的思想，枚举区间内的每个数x，如果x能被最小的质数2整除，再去判断(x/2)是否也能被2整除（筛法思想：利用2将2的所有倍数全部筛掉）；如此下去，如果(x/2)无法被2整除，再去判断它能否被第2小的质数3整除，依次类推。
上一题
下一题