第十四届蓝桥杯省赛C++编程题解;质因数个数

2023-05-18 09:12:17    动态资讯   

提示信息:

因数:又称为约数,如果整数a除以整数b(b0) 的商正好是整数而没有余数,我们就说ba的因数。

质数:又称为素数,一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数。2是最小的质数。

质因数:如果一个数a的因数b同时也是质数,那么b就是a的一个质因数,例如:8=2×2×22就是8的质因数;122×2×323就是12的质因数。

 

题目描述:

给定两个正整数NM1NM1e7),统计NM之间(含NM)每个数所包含的质因数的个数,输出其中最大的个数。

 

例如:

N=6M=10610之间

6的质因数是23,共有2

7的质因数是7,共有1

8的质因数是222,共有3

9的质因数是33,共有2

10的质因数是25,共有2

610之间的数中质因数最多的是8,质因数有3个,故输出3

 

【输入描述】

输入两个正整数NM1NM1e7),两个正整数之间用一个空格隔开

【输出描述】

输出一个整数,表示质因数个数中的最大值

 

【样例输入】

6 10

【样例输出】

3

 

分析:

数学题,考察埃氏筛法。

数据范围非常大,从1~10,000,000,要求时间复杂度为O(n)

 

方法1

暴力枚举每个数+分解质因数,时间复杂度为O(n*sqrt(n)),只能拿到部分分。

 

方法2

埃氏筛,埃氏筛的作用是用筛选的方法找出区间内的素数,具体方法是从小到大枚举质数,剔除它在区间的所有倍数,如此往复就可以确定区间内所有素数。

本题需要在枚举倍数的同时计算当前质数作为因子的个数。

时间复杂度近似为O(n log log n)

 

参考代码:

#include<iostream>
using namespace std;
int a[10000001];
bool b[10000001];
int main(){
  int n,m;
  cin>>n>>m;
  for(int i=2;i*i<=m;i++){
    if(b[i])continue;
    for(int j=2;j<=m/i;j++){
      b[i*j]=1;
      int k=i*j,l=k;
      while(k%i==0){
        k/=i;
        a[l]++;
      }
    }
  }
  int mxn=0;
  for(int i=n;i<=m;i++){
    if(a[i]>mxn)mxn=a[i];
  }
  cout<<mxn;
}