`unsigned long long`太小而不能代表數字？

Question

我一直在努力爲Project Euler得到問題3的答案，在那裏我需要找到600851475143的最大素因子，但是我的程序被掛上了這個數字，而不是更小的（或者有時候更大）。我刪除了程序更普遍的目的，即尋找素數因子分解，希望它能減少計算時間，並可能給我一個答案，但事實並非如此。之前，當程序從1開始而不是輸入時，它給了我最低的素數，17，但僅此而已。現在它沒有給我任何東西。

對於其他人來說，似乎有效的工作是增加數據類型的大小，並在變量末尾添加「ULL」。這不適合我。其他人建議創建一個大數字類，但我還沒有足夠的知識來做到這一點，或者真的能夠與類一起工作。這是該計劃。

#include <iostream> 
using namespace std; 

bool is_prime(unsigned long long int input); 
void factor_number(unsigned long long int input); 

int main() 
{ 
    unsigned long long int input = 600851475143ULL; 

    cout << "Hello World!\n\n"; 

    if (is_prime(input) == false) 
     factor_number(input); 
    else 
     cout << input << 1; 

    cin.get(); 

    return 0; 
} 

bool is_prime(unsigned long long int input) 
{ 
    for (int i = 1; i <= input; i++) 
    { 
     if (i != 1 && i != input) 
     { 
      if (input % i == 0) 
      { 
       return false; 
      } 
     } 
     else if (i == input) 
      return true; 
    } 
} 

void factor_number(unsigned long long int input) 
{ 
    unsigned long long int i = input; 

    while (input % i != 0 || is_prime(i) == false) 
    { 
     i--; 
    } 
    cout << i << endl; 
} 

Answer 1

bool is_prime(unsigned long long int input) 
{ 
    for (int i = 1; i <= input; i++) 

inputunsigned long long int可存儲的值[0,2^64）。

inti可以存儲[ - （2^31），2^31）之間的值。

i時是2,147,483,647和你增加它，它變爲負值，所以循環條件，i <= input永遠是假時input是> = 2^31。如果i是unsigned int，則值> = 2^32時會出現問題。

#include <iostream> 
#include <cstdint> 
#include <limits> 

int main() { 
    int i = std::numeric_limits<int>::max(); 
    std::cout << i << "\n"; 
    ++i; 
    std::cout << i << "\n"; 
} 

現場演示：http://ideone.com/kmeXti

機會是，當，當你比較i和input你的編譯器是給你一個警告，但是您卻選擇忽視它。

您可以修復你的代碼是這樣的：

#include <cstdint> 

bool is_prime(uint64_t input) 
{ 
    for (uint64t_t i = 1; i <= input; ++i) { 

---編輯---

你的首要功能也做這樣的：在一個循環內

for (int i = 1; i <= input; i++) 
{ 
    if (i != 1 && i != input) 
    { 

試驗條件可以是昂貴的（因爲在這種情況下，你對循環的每次迭代都進行測試）。如果你擔心你的代碼的性能，你應該做的第一件事就是儘量消除這些測試。

循環包含i != input測試 - 所以讓葫蘆是進入循環條件：

for (uint64_t i = 1; i < input; i++) 
{ 
    ... 
} 
return true; 

現在我們並不需要測試i != input循環內，但我們還有那個討厭1進行測試。我們可以在開始時添加一些明確的測試：

if (input < 4) { 
    return (input > 1); // 2 and 3 are prime, 0 and 1 are not 
} 

但更重要的是，我們可以快速消除所有的偶數。如果數字的最低位爲「0」，那麼數字是偶數：

if ((input & 1) == 0) // even number 
    return false; 

但是現在我們知道數字不能甚至，我們還可以做的少師測試。全部放在一起：

#include <iostream> 

bool is_prime(uint64_t input) 
{ 
    if (input < 4) 
    { 
     // eliminate 1, 2 and 3. 
     return (input > 1); 
    } 
    // Eliminate even numbers 
    if ((input & 1) == 0) 
     return false; 
    // we've eliminated even numbers, so the smallest 
    // possible divisor is 3, start from there, but 
    // we can also skip all even divisors! 
    for (uint64_t div = 3; div <= input/3; div += 2) 
    { 
     if ((input % div) == 0) 
      return false; 
    } 
    return true; 
} 

int main() 
{ 
    for (uint64_t i = 0; i < 64; ++i) 
    { 
     std::cout << i << ": " << (is_prime(i) ? "yes" : "no") << '\n'; 
    } 
} 

http://ideone.com/aJqApL