Guest User

294.c

a guest
Jul 5th, 2015
239
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<math.h>
  3.  
  4. int isprime(int n){
  5.  
  6.     if(n < 5 || n%2 == 0 || n%3 == 0)
  7.         return (n == 2 || n == 3);
  8.  
  9.     int maxp = sqrt(n) + 2;
  10.     int p;
  11.     for(p = 5; p < maxp; p+= 6){
  12.         if(n%p == 0 || n % (p+2) == 0) return 0;
  13.     }
  14.     return 1;
  15. }
  16.  
  17. int main(){
  18.  
  19.     int N,n;
  20.     int L,U,D,P;
  21.  
  22.    
  23.     int i,j,s;
  24.     int count;
  25.     int maxp, p;
  26.     int acc;
  27.     scanf("%d", &N);
  28.  
  29.    
  30.     for(n = 0; n < N; n++){
  31.        
  32.        
  33.  
  34.  
  35.         scanf("%d%d", &L, &U);
  36.  
  37.        
  38.         D = 0;
  39.         for(i = L; i <= U; i++){
  40.             count = 0;
  41.             acc = 1;
  42.             j = i;
  43.            
  44.             for(; j%2 == 0; j/=2)
  45.                 count++;
  46.  
  47.             acc *= count+1;
  48.  
  49.  
  50.             j = i;
  51.             count = 0;
  52.             for(; j%3 == 0; j/=3)
  53.                 count++;
  54.  
  55.             acc *= count+1;
  56.            
  57.            
  58.             maxp = sqrt(i) + 2;
  59.             for(p = 5; p < maxp; p++){
  60.  
  61.                 if(isprime(p)){
  62.                     count = 0;
  63.                     j = i;
  64.                     for(; j%p == 0; j/=p)
  65.                         count++;
  66.  
  67.                     acc *= count+1;
  68.                 }
  69.             }
  70.  
  71.             if(acc > D){
  72.                 D = acc;
  73.                 P = i;
  74.             }
  75.  
  76.         }
  77.        
  78.    
  79.  
  80.         printf("Between %d and %d, %d has a maximum of %d divisors.\n",L, U, P, D);
  81.            
  82.     }
  83.  
  84.  
  85.     return 0;
  86. }
RAW Paste Data