爲什麼是錯誤的答案烏瓦：Factovisors

Question

有關弗吉尼亞大學在線評測問題10139 - Factovisors，2號n和m給出的，我們需要檢查是否m分n!。

我用的算法：

1. 生成素數，直到常量數

2. 採取m，並得到其質數因子

3. 對於m的因素每一個素，計算getpower功能對於n並對它們進行比較

我測試了不同的情況，它給我錯誤的答案，任何建議？

這裏是我的代碼：

bool Factovisor (int n, int m) { 

/* Special Cases */ 

    if(n==0 && m!=1) 
     return false; 
    else if(n==0&&m==1) 
     return true; 
    else if(m==0) 
     return false; 
    else if(m==n||m==1) 
     return true; 
    else if (n >= m) 
     return true; 
    else { 

     vector <factores> factores_in_m; 
     int index = 0; 
     int k=m; 
/* first I generate all primes in primes vector */ 

     for (int i = 0; i < primes.size(); i++) { 
      if (primes[i] > k) { 
       break; 

      } else { 
/* factores is struct contain the prime and count*/ 

       factores f = {primes[i], 0}; 
       while (k % primes[i] == 0) { 
        f.count += 1; 
        k = k/primes[i]; 
       } 

       if (f.count) { 
        factores_in_m.push_back(f); 
       } 
      } 
     } 

     if (k > 1) { 
      if (n < k) { 
       return false; 
      } else { 
       factores f; 
       f.prime= k; 
       f.count =1; 
       factores_in_m.push_back(f); 
      } 
     } 

     for (int i = 0; i < factores_in_m.size(); i++) { 
      if (factores_in_m[i].count - get_powers(n, factores_in_m[i].prime) > 0) { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

int get_powers (int n, int p) { 
    int result = 0, power = p; 
    while (power <= n) { 
     result += n/power; 
     power =power* p; 
    } 
    return result; 
} 

bool isPrime (int n) { 
    for (int i = 2; i < n; i++) { 
     if (n % i == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

void get_prime() { 
    for (int i = 2; i < maxn0; i++) { 
     if (isPrime(i)) { 
      primes.push_back(i); 
     } 
    } 
} 

Answer 1

編輯：錯誤的答案，由於問題的misanderstanding。

9分7！但是你的算法會回答錯誤，因爲get_powers(7, 3) == 0和3是因子9.

這不是你的實現，而是你的算法錯了。

Answer 2

也許你的黃金世代是錯誤的，但當然你的get_powers執行易受到溢出。

int get_powers (int n, int p) { 
    int result = 0, power = p; 
    while (power <= n) { 
     result += n/power; 
     power =power* p; 
    } 
    return result; 
} 

如果int是，因爲它通常是，一個32位寬的類型，素數大於46341大的計算power = power * p;溢出第一次完成。這可能會導致錯誤的結果，例如

get_powers(10000000, 131071) 

返回52如果溢出的行爲是環繞模2 ，但正確的結果將是76.現在，由於m小於2 ，這個特定的一個不會受到傷害，因爲m不能被131071²整除。但在環繞行爲，

get_powers(1000000, 699733) = -2192 

是負的，所以對於n = 1000000和m = 2*699733例如，你會錯誤地得出結論：n!是不是m整除。

爲了避免可能的溢出，只有p劃分，

int get_powers(int n, int p) { 
    int result = 0; 
    n /= p; 
    do { 
     result += n; 
     n /= p; 
    }while(n > 0); 
    return result; 
} 

---

從評論：

我編輯添加我的函數來得到的素數，直到常數 「maxn0」 - userG 2小時前

您爲maxn0選擇了什麼值？ - 丹尼爾·菲捨爾3小時前

maxn0 = 10000

該值太小。

隨着素數爲10000，你只能保證正確factorise數不超過10 （當然，因爲下一任是10007，數字比10007² = 100140049小），但限制給出2 ，這是更大的。

只要數字m給出兩個（不一定是不同的）主因子大於10000時，就不會正確地將其分解，並且這通常會導致錯誤的答案。

你需要的所有素數≤ √（2 -1），這是所有質數< 46340獲得所有允許m正確因式分解。