2018/12/15

a010: 因數分解

a010: 因數分解




#include
#include

int main ()
{
  int n, nn;

  while (scanf ("%d", &n) == 1) {
    int last = -1;
    int cnt=1;
    nn = sqrt(n);
    // 因為所有質因數只有2是偶數，先處理2
    while (!(n % 2)) {
      n >>= 1;
      if (last != 2) {
        printf ("2");
        last = 2;
        cnt = 1;
      } else cnt++;
    }
    if (cnt > 1) {
      printf ("^%d", cnt);
      cnt = 1;
    }
    for (int i = 3; i <= nn;) {
      if (n % i == 0) {
        n /= i;
        if (last != i) {
          if (cnt > 1) printf ("^%d * %d", cnt, i);
          else {
            if (last <= 0) printf ("%d", i);
            else printf (" * %d", i);
          }
          cnt = 1;
        } else cnt++;
        last = i;
      } else i += 2;
    }
    if (cnt > 1) {
      if (n > 1)
        printf ("^%d * %d\n", cnt, n);
      else
        printf ("^%d\n", cnt);
    } else if (n > 1) {
      if (last <= 0)
        printf ("%d\n", n);
      else
        printf (" * %d\n", n);
    } else puts("");
  }
  return 0;
}




上面的速度應該是比較快的，底下還有一個比較簡明的版本




#include
#include
#define push(n) fac[facn++] = (n)

int fac[1024];
int facn = 0;

void output() {
  int last = -1;
  int cnt = 0;
  for (int i=0; i 1) { // 有指數
        printf ("^%d * %d", cnt, fac[i]);
      } else {
        if (last <= 0) // 第一個
          printf ("%d", fac[i]);
        else // 不是第一個，沒有指數
          printf (" * %d", fac[i]);
      }
      cnt = 1;
    } else { cnt++; }
    last = fac[i];
  }
  if (cnt > 1) printf ("^%d\n", cnt); else printf ("\n");
}

int main ()
{
  int n, i, nn;

  while (scanf ("%d", &n) == 1) {
    facn = 0;
    nn = sqrt(n);
  
    // 因為所有質因數只有2是偶數，先處理2
    while (!(n % 2)) {
      n >>= 1;
      push(2);
    }
    for (i = 3; i <= nn; i+=2) {
      if (n % i == 0) {
        n /= i;
        push(i);
        i-=2;
      }
    }
    if (n > 1) push(n);
    output();
  }
  return 0;
}













張貼者：
菠蘿麵包


於
12/15/2018



































0
意見:
        








張貼留言















訂閱：
張貼留言 (Atom)