hdu hdoj 1406 完数.doc

问题描述 完数 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9129????Accepted Submission(s): 3047 Problem Description 完数的定义：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个数是完数，比如6，28都是完数：6=1+2+3；28=1+2+4+7+14。本题的任务是判断两个正整数之间完数的个数。 ? Input 输入数据包含多行，第一行是一个正整数n，表示测试实例的个数，然后就是n个测试实例，每个实例占一行，由两个正整数num1和num2组成,(1num1,num210000) 。 ? Output 对于每组测试数据，请输出num1和num2之间（包括num1和num2）存在的完数个数。 ? Sample Input 2 2 5 5 7 ? Sample Output 0 1 ? Author lcy ? Source 杭电ACM集训队训练赛（IV） ? Recommend Ignatius.L 问题分析与算法实现 参考代码 #include iostream #include cmath #define MAX 10000 using namespace std; int i,j; int len=0; int Prime[MAX/3],NotPrime[MAX]; void GetPrime() { for(i=2;iMAX;i++) { if(NotPrime[i]==0) { Prime[len++]=i; } for(j=0;jlenPrime[j]*iMAX;j++) { NotPrime[Prime[j]*i]=1; if(i%Prime[j]==0) break; } } } int Perfect[MAX+1]; void GetPerfectNumber() { int i,sum; int a,m; int N; GetPrime(); for (i=2;i10001;i++) { m=0; sum=1; N=i; while(N1) { a=0; while(N%Prime[m]==0) { N/=Prime [m]; a++; } if(a0) { sum=sum*(pow(Prime[m],(a+1))-1)/(Prime[m]-1); } m++; } Perfect[i]=Perfect[i-1]; if(sum==2*i) { Perfect[i]++; } } } int main() { int n; int a,b,temp; GetPerfectNumber(); cinn; while(n--) { cinab; if(ab) { temp=a; a=b; b=temp; } coutPerfect[b]-Perfect[a-1]endl; } return 0; } #pragma warning (disable:4786) #include iostream #include set using namespace std; //求330以内的所有素数 int len; const int MAX=330; bool Notprime[MAX]; int prime[MAX/3]; void get_prime() { len=0; int i,j; for(i=2;i