来自厦大软件工程何大佬的作业题
图片来自何dalao（数据规模小于500w）
鉴于10s的时限，直接循环暴力一遍即可通过
当然不是简单的暴力，是有优化的暴力
需要注意的是，判断约数个数时可以使用素数优化的方法，即
图片来自何dalao
先打一个2300内的素数表（因为2300的平方大于500w）
然后根据每一位数进行约数个数的判断，具体方法是对素数表中的数进行逐个逐个判断，能整除则对当前的数字进行整除，将计数的变量加一，直到无法整除为止，将变量得到的数和存储当前约数个数的数字相乘，然后对下一位进行判断。
如果该数的约数个数大于之前所得到的数字的约数个数，则对其进行更新。
需要注意的是，可能某一数字最后会余下一个素数 无法被2300内的素数整除，所以在对2300内的素数数字循环后要进行特殊判断（何dalao就被这一点坑了）。
代码就不贴了因为我没写orz。
17/12/10 更新代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<stdio.h> #include<math.h> #include<string.h> #include<stdbool.h> int prime[10001]; int num_prime; int calc_prime() { int cnt=0; for(int i=2;i<=2300;i++) { bool flag=1; for(int j=2;j<(int)sqrt(i);j++) if(i%j==0) { flag=0; break; } if(flag)prime[cnt++]=i; } return cnt; } int calc_ys(int n) { int ans=1; for(int i=0;i<num_prime&&n!=1;i++) { int cnt=0; while(n%prime[i]==0) { cnt++; n/=prime[i]; } ans*=(cnt+1); } if(n!=1)ans*=2; return ans; } int main() { int a,b; num_prime=calc_prime(); scanf("%d%d",&a,&b); int max=0; for(int i=a;i<=b;i++) { int t=calc_ys(i); max=max>t?max:t; } printf("%d\n",max); return 0; } |