Finding the largest prime factor? (Doesn't work in large number?)

user_12809529 0
Viewed 55

I am a beginner in C++, and I just finished reading chapter 1 of the C++ Primer. So I try the problem of computing the largest prime factor, and I find out that my program works well up to a number of sizes 10e9 but fails after that e.g.600851475143 as it always returns a wired number e.g.2147483647 when I feed any large number into it. I know a similar question has been asked many times, I just wonder why this could happen to me. Thanks in advance.

P.S. I guess the reason has to do with some part of my program that is not capable to handle some large number.

#include <iostream>

int main()
{
    int val = 0, temp = 0;
    std::cout << "Please enter: " << std::endl;
    std::cin >> val;
    for (int num = 0; num != 1; val = num){
        num = val/2;
        temp = val;
        while (val%num != 0)
            --num;
    }
    std::cout << temp << std::endl;
    return 0;
}
c++
2 Answers

Your int type is 32 bits (like on most systems). The largest value a two's complement signed 32 bit value can store is 2 ** 31 - 1, or 2147483647. Take a look at man limits.h if you want to know the constants defining the limits of your types, and/or use larger types (e.g. unsigned would double your range at basically no cost, uint64_t from stdint.h/inttypes.h would expand it by a factor of 8.4 billion and only cost something meaningful on 32 bit systems).

user_3646960

2147483647 isn't a wired number its INT_MAX which is defined in climits header file. This happens when you reach maximum capacity of an int.

You can use a bigger data type such as std::size_t or unsigned long long int, for that purpose, which have a maximum value of 18446744073709551615.

user_179394550
Related