如何分解數字？

Question

我被要求分解一個數字並以特定的方式顯示它。

例如：100 = 2^2 * 5^2

這是我與沒有骰子迄今所使用的C++代碼，不幸的是：

#include <stdio.h> 
#include <math.h> 

//IsPrime indicates whether a given number is or is not prime. 
bool IsPrime(long long n) 
{ 
    int j = 3; 
    if (n == 2) 
    { 
     return true; 
    } 
    else if (n % 2 == 0) 
    { 
     return false; 
    } 
    else 
    { 
     for (j = 3; j <= sqrt(n); j += 2) 
     { 
      if (n%j == 0) 
      { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

int main(void) 
{ 
    long long n_orig,n, i=3 , primecount=0; 
    scanf("%lld", &n_orig); 
    n = n_orig; 
    if (n == 1) 
    { 
     printf("1"); 
     return 0; 
    } 
    if (IsPrime(n)) 
    { 
     printf("%lld", n); 
     return 0; 
    } 
    if (n % 2 == 0) 
    { 
     while (n >= 2 && n % 2 == 0) 
     { 
      primecount++; 
      n = n/2; 
     } 
     if (primecount == 1) 
     { 
      printf("2*"); 
     } 
     else 
     { 
      printf("2^%lld*", primecount); 
     } 
    } 
    primecount = 0; 
    n = n_orig; 
    while (i <= n/2) 
    { 
     if (IsPrime(i)) 
     { 
      while (n >= i && n % i == 0) 
      { 
       primecount++; 
       n = n/i; 
      } 
     } 
     n = n_orig; 
     if (primecount == 0) 
     { 
      i++; 
      continue; 
     } 
     if (primecount == 1) 
     { 
      printf("%lld*", i); 
     } 
     else 
     { 
      printf("%lld^%lld*", i, primecount); 
     } 
     primecount = 0; 
     i+=2; 
    } 
    printf("\b"); 
    return 0; 
} 

使用這個代碼我能夠生成一些測試用例，但是當我將我的答案上傳到可能評估代碼的網站時，在7個測試用例中（我不知道它們究竟是什麼），我通過3,失敗3和超過時間限制（在問題中甚至沒有聲明）在一個案例中。我真的很感激一些幫助，請小老虎友好！

此外，我並不想知道我的答案是否可以在某種程度上得到改善，我現在的首要任務是理解爲什麼我自己的代碼無法按預期工作。

P.S：的iostream和陣列 S的用法是不允許的。

在此先感謝。

Answer 1

試試這個：

#include <stdio.h> 
#include <math.h> 

unsigned long long PrintMultiplicity(unsigned long long n,unsigned long long factor) 
{ 
    unsigned int count = 0; 

    while (n%factor == 0) 
    { 
     count++; 
     n /= factor; 
    } 

    if (count > 0) 
    { 
     printf("%llu^%u",factor,count); 
     if (n > 1) 
      printf("*"); 
    } 

    return n; 
} 

void PrintFactorization(unsigned long long n) 
{ 
    unsigned long long factor; 
    unsigned int add; 

    printf("%llu = ",n); 

    n = PrintMultiplicity(n,2); 
    n = PrintMultiplicity(n,3); 

    // Check only factors that are adjacent to multiples of 6 
    for (factor = 5, add = 2; factor <= sqrt(n); factor += add, add = 6-add) 
     n = PrintMultiplicity(n,factor); 

    if (n > 1) 
     printf("%llu^1",n); 

    printf("\n"); 
} 

int main() 
{ 
    unsigned long long n; 
    scanf("%llu",&n); 
    PrintFactorization(n); 
    return 0; 
} 

Answer 2

您需要執行一些優化優化。不要爲每個值調用isPrime()方法，而應考慮採用不同的方法，以便在開始時可以完全忽略不相關的值。

1. 獲取自帶有關質數號碼的列表n下，使用Sieve of Eratosthenes概念。從列表中的最低值黃金

2. 開始，分n得到中間值作爲

   n/lowest_prime_that_perfectly_divide_n。

   繼續執行此操作，檢查下一個較高的素數值，直到n變爲1。這樣你就有計數的每個分解因素。

Answer 3

您不需要進行初步測試，並且質數或主輪的列表僅用於加速。列出所有主要因素的簡單程序是

#include <stdio.h> 
#include <math.h> 

int main(void) 
{ 
    long long n_orig,n,k; 
    scanf("%lld", &n_orig); 
    n = n_orig; 
    k=2; 
    while(k*k<=n) { 
     while(0==n%k) { 
      n = n/k; 
      printf("%lld ",k); 
     } 
     k++; 
    } 
    if(n>1) printf("%lld ",n); 
    printf("\n"); 
    return 0; 
} 

這不會生成所需的輸出格式，但可以輕鬆添加到該格式中。