#UVa:583-Prime Factors

灆洢 2014-10-07 16:06:49

建立質數表做質因數分解即可得解。

C++(0.902)

/*******************************************************/
/* UVa 583 Prime Factors                               */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2014/10/07                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  bool composite[50000] = {true, true, false};
  for( int i = 2 ; i < 50000 ; ++i ){
    if( !composite[i] ){
      for( int j = i+i ; j < 50000 ; j+=i ){
        composite[j] = true;
      }
    }
  }

  int g;
  while( scanf("%d", &g) != EOF && g != 0 ){
    printf( "%d = ", g );

    bool print_mul = false;
    if( g < 0 ){
      printf("-1");
      print_mul = true;
      g *= -1;
    }

    for( int i = 2 ; i < 50000 ; ++i ){
      if( !composite[i] ){
        while( g % i == 0 ){
          if( print_mul ) printf(" x ");
          printf("%d", i);
          print_mul = true;
          g /= i;
        }
      }

      if( g == 1 ) break;
    }

    if( g != 1 ){
      if( print_mul ) printf(" x ");
      printf( "%d", g );
    }

    printf("\n");
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料