算法导论中的题目，老师让用素数去实现查找最大约数个数
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> #include<math.h> using namespace std; #define ll long long const int INF=0x7fffffff; const int N=100000+2; int prime[1005]; void is_prime() //素数打表 { int i,j; memset(prime,0,sizeof(prime)); for (i=2;i*i<=1000;i++) { if (!prime[i]) for (j=i*i;j<=1000;j+=i) prime[j]=1; } } int fun(int n) //求约数个数 { int i,tmp,sum=1; if (!prime[n]) return 2; for (i=2;i<=n/2;i++) { tmp=n; int cnt=0; if (tmp%i==0&&!prime[i]) { while (tmp%i==0) { cnt++; tmp/=i; } } sum*=(1+cnt); } return sum; } int main() { int n,i,l,r,cnt=0; is_prime(); scanf("%d%d",&l,&r); for (i=l;i<=r;i++) if (cnt<fun(i)) cnt=fun(i); printf("%d\n",cnt); return 0; }