2019年海淀区青少年程序设计挑战活动的小学组题目大家觉得怎么样呢，是不是还是有一些小小难度的呢。今天我们来看一下2019年北京市科普日朝阳区选拔赛的小学组的题目。今天先来前两道。
小橙teacher会持续为大家分享青少年信息学的案例与题解，请多多关注与分享哦！！！
1
问题描述
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≤50000
2
问题分析
今天我们详细来说一下什么是质数以及质因数分解的问题。
质数也称为素数。一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）；否则称为合数。注意，最小的质数（素数是2），1既不是质数也不是合数。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积。
如果要求一个整数的所有质因数的问题，我们可以简单举几个例子来观察规律。
比如：
8= 2*4=2*2*2；
18 = 2*9 = 2*3*3；
……
我们可以看出求一个数所有质因数的过程就是从i等于整数2开始判断，看是否能整除n，如果n能够被一个素数整除，那么判断n/i的商是不是素数，如果不是素数，那么继续以同样的方法求n/i的商的所有质因数；如果n/i的商也是素数，那么所有的质因数都被找出来了，结束搜索判断。
我们再看这道题，这道题的要求是求一个数的所有质因数都不大于指定的数字A。看在[N，N+M]的区间内有多少这样的数字。其实就是在求质因数分解的过程中加上一个判断，判断这个质因数是否大于A即可。
3
参考代码如下
#include <iostream>
#include <cmath>
using namespace std;
//判断一个数的所有质因子,如果满足所有质因子都不大于a,则返回1，否则0
int prime_factor(int n,int a){
for(int i = 2; i <=sqrt(n); i++) {
//判断i是否能被整除
while(n % i == 0) {
//若能整除，则判断该因子是否大于a ,若是，则直接返回0
if(i > a){
return 0;
}
//若该因子不大于a,则去掉该因子后接着找其他的因子
n /= i;
}
}
if(n!=1) {
//当n!=1时，n为最后一个质因子 //判断n为质因子时是否也大于a，若是，则直接返回0
if(n > 5){
return 0;
}
}
//都不大于a,返回1即可
return 1;
}
int main() {
int n,m,a,cnt=0;
cin >> n >> m >> a;
//依次判断n到n+m之间的所有数
for(int i = n;i<=n+m;i++){
if(prime_factor(i,a)){
cnt++;
}
}
cout << cnt << endl;
return 0;
}
转自公众号：
信息学少儿编程