`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