294-Divisors

<br /> /* <br /> "Divisors"<br /> Level:6.0<br /> Date:2006/9/23<br /> 技巧：這題的技巧是先取得最小質數表(用Eratosthenes法找質數),<br /> 然後利用(i+1)*(j+1)*(k+1).... 其中i,j,k是質因數的指數,<br /> 如:100 = 2^2 * 5^2 ,所以100有(2+1)*(2+1)=9個 positive divisor <br /> 然後找range裡最大的divisor,其中要考慮到range本身便是質數，如: 3 3 <br /> 及range為1 1的special case. <br /> */<br /> <br /> #include <stdio.h><br /> #define N 31622<br /> #define PNUM 3402<br /> <br /> void getPrime(void);<br /> int prime[PNUM]={0};<br /> <br /> main(){ <br /> int range=0,<br /> lowBound=0,upperBound=0,<br /> i=0,k=0,<br /> count=0,ans=1,dividend=0,max=0,target=0; <br /> getPrime();<br /> scanf("%d",&range);<br /> while(range-- > 0){<br /> max=target=0;<br /> scanf("%d %d",&lowBound,&upperBound);<br /> for(i=lowBound;i <= upperBound;i++){ dividend = i; k=0; ans=1; do{ while(dividend%prime[k]==0){ count++; dividend/=prime[k]; } if(count > 0 || i==1){<br /> ans *= count+1; <br /> } <br /> count=0; <br /> }while(prime[k] <= dividend && prime[k]*prime[k] <= i && ++k < PNUM-1); if(dividend!=1) //there are two divisor when number in range is a prime. ans*=2; if(max < ans){ max = ans; target = i; } } printf("Between %d and %d, %d has a maximum of %d divisors.\n" 　　　　　　,lowBound,upperBound,target,max); } } /*Using Eratoshenes method to calculate prime*/ void getPrime(void){ int n[N+1]={0},i=0,j=0; for(i=2;i*i <= N;i++){ for(j=i*2;j <= N;j++){ if(j%i == 0) n[j]=1; // 1,if n[j] is not a prime. } } j=0; for(i=2;i < N;i++){ if(n[i] == 0){ prime[j++] = i; //Collect all of prime. } } }