Maximal Common Divider

Language: English
Programming Language: C++
Published by: oscarp [not registered]
Last Update: 5/15/2006
Views: 137

Description

With this class you can find the maximal common divider of several numbers. Simply create the object and call the 'calculate' method. You've to give it two parameters: the array of number from which you want to calculate the mcd and the quantity of numbers.

Code

Display line numbers

1 /******* FILE MaximaCommonDivider.h **************************/ 2 3 #ifndef MAXIMAL_COMMON_DIVIDER 4 #define MAXIMAL_COMMON_DIVIDER 5 6 /** This class calculates the maximal common divider 7 * of an array of integers. 8 * Simply create the object and then call it's "calculate" 9 * method giving th array of numbers from which you want to 10 * calculate it and the quantity of them. 11 * 12 * 13 * Author: Oscar Perez del Campo 14 * os_carp@terra.es 15 * 16 */ 17 18 #include <stdlib.h> 19 #ifndef MIN 20 #define MIN(A,B) (A<B)?A:B 21 #endif 22 23 class MaximalCommonDivider 24 { 25 public: 26 MaximalCommonDivider(); 27 ~MaximalCommonDivider(); 28 29 public: 30 int calculate(int *numbers, int howMany); 31 32 private: 33 /** This method calculates the dividers of 'number' 34 * and puts them into 'dividers'. It allocates memory 35 * to store them. 36 * Returns the number of items in 'dividers'. 37 */ 38 int getDividers(int number, int **dividers); 39 40 /** This method fussionates dividers contained in '**dividers' 41 * and in '*newDividers' and let them in '**dividers'. 42 */ 43 void fussionateDividers(int **dividers, 44 int *numberOfDividers, 45 int *newDividers, 46 int numberOfNewDividers); 47 48 /** This method multiplies a given vector of 'len' integers 49 * and returns the result. 50 */ 51 int multiplyVector(int *vector, int len); 52 53 /** Call this method with a prime number and it will give back the next 54 * prime number. 55 */ 56 int getNextPrime(int actual); 57 58 /** This method returns 1 if given number is prime, 59 * 0 otherwise. 60 */ 61 int isPrime(int number); 62 }; 63 64 #endif 65 66 /******* END OF FILE MaximaCommonDivider.h **************************/ 67 68 /******* FILE MaximaCommonDivider.cpp **************************/ 69 #include "MaximalCommonDivider.h" 70 #include <stdio.h> 71 72 MaximalCommonDivider::MaximalCommonDivider() 73 { 74 } 75 76 /************************************************************************/ 77 78 MaximalCommonDivider::~MaximalCommonDivider() 79 { 80 } 81 82 /************************************************************************/ 83 84 int MaximalCommonDivider::calculate(int *numbers, int howMany) 85 { 86 int *dividers; 87 int *newDividers; 88 int i; 89 int numberOfDividers; 90 int numberOfNewDividers; 91 int value; 92 93 if (howMany>0) 94 { 95 numberOfDividers = getDividers(numbers[0],&dividers); 96 for (i=1;i<howMany;i++) 97 { 98 numberOfNewDividers = getDividers(numbers[i],&newDividers); 99 fussionateDividers(&dividers,&numberOfDividers, 100 newDividers,numberOfNewDividers); 101 free(newDividers); 102 } 103 value = (multiplyVector(dividers,numberOfDividers)); 104 } 105 else 106 { 107 value = 0; 108 } 109 return(value); 110 } 111 112 /************************************************************************/ 113 114 void MaximalCommonDivider::fussionateDividers(int **dividers, 115 int *numberOfDividers, 116 int *newDividers, 117 int numberOfNewDividers) 118 { 119 int i; 120 int j; 121 int k; 122 123 int *final; 124 final = (int*)malloc(sizeof(int)*MIN(*numberOfDividers,numberOfNewDividers)); 125 i=0; 126 j=0; 127 k=0; 128 while ((i<*numberOfDividers) && (j<numberOfNewDividers)) 129 { 130 if ((*dividers)[i]==newDividers[j]) 131 { 132 final[k]=newDividers[j]; 133 k++; 134 j++; 135 i++; 136 } 137 else 138 { 139 //incrementem el menor 140 if ((*dividers)[i]>newDividers[j]) 141 { 142 j++; 143 } 144 else 145 { 146 i++; 147 } 148 } 149 } 150 *dividers=(int*)realloc(*dividers,sizeof(int)*k); 151 for (i=0;i<k;i++) 152 { 153 (*dividers)[i] = final[i]; 154 } 155 *numberOfDividers = k; 156 } 157 158 /************************************************************************/ 159 160 int MaximalCommonDivider::getDividers(int number, int **dividers) 161 { 162 int howMany; 163 int d; 164 howMany = 0; 165 d = 2; 166 *dividers = NULL; 167 while (number>1) 168 { 169 if (number % d==0) 170 { 171 howMany++; 172 *dividers = (int*)realloc(*dividers,sizeof(int)*howMany); 173 (*dividers)[howMany-1] = d; 174 number /= d; 175 } 176 else 177 { 178 d = getNextPrime(d); 179 } 180 } 181 howMany++; 182 *dividers = (int*)realloc(*dividers,sizeof(int)*howMany); 183 (*dividers)[howMany-1] = 1; 184 return(howMany); 185 } 186 187 /************************************************************************/ 188 189 int MaximalCommonDivider::multiplyVector(int *vector, int len) 190 { 191 int i; 192 int value; 193 value = 1; 194 for (i=0;i<len;i++) 195 { 196 value *= vector[i]; 197 } 198 return(value); 199 } 200 201 /************************************************************************/ 202 203 int MaximalCommonDivider::getNextPrime(int actual) 204 { 205 actual++; 206 while (!isPrime(actual)) 207 { 208 actual++; 209 } 210 return(actual); 211 } 212 213 /************************************************************************/ 214 215 int MaximalCommonDivider::isPrime(int number) 216 { 217 int i; 218 int result; 219 int max; 220 max = number /2; 221 result = 1; 222 i=2; 223 while ((result) && (i<max)) 224 { 225 result = ((number % i) != 0); 226 i++; 227 } 228 return(result); 229 } 230 231 232

Maximal Common Divider

Description

Code

No comments avaiable

Add a comment