Advertisement
NovaYoshi

simplify square root

Apr 19th, 2011
330
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.29 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. // 180
  6. // 3 3 5 2 2
  7.  
  8. // 6 sqrt (5)
  9.  
  10. int FPartZero(float N) {
  11.   if(ceil(N) != N) return(0);
  12.   return(1);
  13. }
  14. int FindOneFactor(unsigned char Byte) {
  15.   int i;
  16.   for(i=2; i<Byte ; i++ )
  17.     if(FPartZero((float)Byte / i))
  18.       return(i);
  19.   return(-1);
  20. }
  21.  
  22. typedef struct TreeNode{
  23.   unsigned char A;
  24.   struct TreeNode *X;
  25.   struct TreeNode *Y;
  26. } TreeNode;
  27.  
  28. TreeNode *NewNode(unsigned char A) {
  29.   TreeNode *Poke = (TreeNode*)malloc(sizeof(TreeNode));
  30.   if(Poke == NULL) abort();
  31.   Poke->A = A;
  32.   Poke->X = NULL;
  33.   Poke->Y = NULL;
  34.   return(Poke);
  35. }
  36.  
  37.  
  38. void ConstructTree(TreeNode *Now) {
  39.   int Div = FindOneFactor(Now->A);
  40.   if(Div == -1) { // prime
  41.     Now->X = NULL;
  42.     Now->Y = NULL;
  43.     return;
  44.   }
  45.   else {
  46.     Now->X = NewNode(Div);
  47.     Now->Y = NewNode(Now->A/Div);
  48. //    printf(" %i / %i = %i \n", Now->A, Now->X->A, Now->Y->A);
  49.     ConstructTree(Now->X);
  50.     ConstructTree(Now->Y);
  51.   }
  52. }
  53. void TraverseTree(TreeNode *Now, char *Count) {
  54.   if(Now->X == NULL || Now->Y == NULL) {
  55.     Count[Now->A]++;
  56.     return;
  57.   }
  58.   TraverseTree(Now->X, Count);
  59.   TraverseTree(Now->Y, Count);
  60.   free(Now);
  61. }
  62. short SimplifySqrt(unsigned char Byte) {
  63.   unsigned short Lo, Hi; double F;
  64.   unsigned char CountOfEachFactor[256];
  65.   memset(CountOfEachFactor, 0, 256);
  66.  
  67.   Lo = Hi = 0;
  68.   printf("%i - ", Byte);
  69.   if(FPartZero(sqrt((float)Byte))) {
  70.     printf("perfect! ");
  71.     Lo = Byte;
  72.     Hi = 0;
  73.   }
  74.   else {
  75.     TreeNode *Seed = (TreeNode*)malloc(sizeof(TreeNode));
  76.     Seed->A = Byte;
  77.     ConstructTree(Seed);
  78.     printf("tree made? - ");
  79.     TraverseTree(Seed, CountOfEachFactor);
  80.     printf("tree counted? -");
  81.     Lo = 1;
  82.     int i, j;
  83.  
  84.     for(i=0;i<256;i++) {
  85.       j = 0;
  86.       while(CountOfEachFactor[i] >= 2) {
  87.         CountOfEachFactor[i]-=2;
  88.         j++;
  89.       }
  90.       if(j) {
  91.         Lo*=(j*i);
  92.       }
  93.     }
  94.  
  95.     Hi = 1;
  96.     for(i=0;i<256;i++) {
  97.       j = 0;
  98.       while(CountOfEachFactor[i] > 0) {
  99.         CountOfEachFactor[i]--;
  100.         Hi*=i;
  101.       }
  102.     }
  103.  
  104.   }
  105.  
  106.   printf("- %i*sqrt(%i) \n", Lo, Hi);  
  107. }
  108.  
  109. int main() {
  110.   printf("%i \n", FindOneFactor(90));
  111.  // SimplifySqrt(48);
  112.  // SimplifySqrt(56);
  113.  // SimplifySqrt(90);
  114.  // SimplifySqrt(81);
  115.   SimplifySqrt(180);
  116.  
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement