0

The below program is to check whether a number (say "n") prime factors are limited to 2,3,and 5 only or not. But program gives me signed integer overflow runtime error. Can anyone please help me in solving this problem? Here's the piece of code:

 bool check(int n)
   {
       if(n<0)
       n=n*(-1); // If 'n' is negative, making it positive.
       int count=1; //'count' variable to check whether the number is divisible by 2 or 3 or 5.
       while(n!=1 && count)
       {
           count=0;
           if(n%2==0)
           {
               n/=2; count++;
           }
           else if(n%3==0)
           {
               n/=3; count++;
           }
           else if(n%5==0)
           {
               n/=5; count++;
           }
       }
       if(n==1)
       return true;
       else return false;
       
    }

Program gave me this error:

runtime error: signed integer overflow: -2147483648 * -1 cannot be represented in type 'int'

Improve this question
6
  • Then maybe you want a 64 bit int like: int64_t instead of a 32 bit int Commented Nov 18, 2022 at 17:33
  • 1
    32 bit integer can represent from -2,147,483,648 through positive 2,147,483,647 hense overflow. You just need bigger type, use long or long long Commented Nov 18, 2022 at 17:35
  • 3
    maximum value for int MAX_INT if int is 32bit equals to 2^31 -1 = 2147483647 Commented Nov 18, 2022 at 17:35
  • 1
    The range of values for a 2's compliment signed 4 byte integer is -2147483648 to 2147483647. As you can see, there is no representation for 2147483648. Either use a larger integer type, which eliminates the immediate problem but still has an upper value limit, or restrict the parameter to a range greater than -2147483648. Commented Nov 18, 2022 at 17:37
  • Side note: Look into prime number sieving algorithms like the Sieve of Eratosthenes for higher-performance prime number verification. You generate a table with the sieve once at program start up, and then simply check the table for all of the queries in the future. Commented Nov 18, 2022 at 17:46

2 Answers 2

Reset to default
1

-2147483648 * -1 cannot be represented in type 'int' [signed 32 bit]

For sure, it cannot, and you know why? A simple fact of representation.

Imagine to have 4 bits instead of 32. You would have 1 bit for the sign and 3 for the absolute value, right?

Well, lets say you have 0 for positive numbers and 1 for negative numbers in the first bit.

Then you can only represent 2^3=8 combinations for the absolute value, right? Well, you only have 8 positive numbers and 8 negative numbers.

BUT 0 is considered as positive, so you have 8 negative, 7 positive and 1 neutral. So you have numbers from -8 to 7.

In this case you have numbers from -2147483648 to 2147483647.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Calling the non-sign-bits of an integer the mantissa is pretty weird, IDK what to call them but at least not that
Yes @harold I knew it wasn't the correct term, it's used for IEEE754 if I remember well... I'll edit to call it "absolute value", then it should be an acceptable answer I think, right?
Perhaps, but that term suggests that x & 0x7FFFFFFF computes the absolute value of x and it doesn't
Well, I said it many times, but perhaps that matematicians back in 50s should have simply wasted that damn bit for the negative 0 😅
0

If your prime factors are limited to be 2, 3, or 5, then the easiest way is:

if (n < 0) return false;

But if your prime factors can also be -1, then just make that as an acceptable valid terminal condition.

bool check(int n) {
    for (;;) {
        if (n%2 == 0) {
            n /= 2;
        } else if (n%3 == 0) {
            n /= 3;
        } else if (n%5 == 0) {
            n /= 5;
        } else {
            break;
        }   
    }   

    return (n == 1) || (n == -1);
}
Improve this answer

1 Comment

Until recently, when n is negative, n/2 can have either of two values, depending on whether the code (i.e., the hardware) rounds down or toward zero. For example, after n = -3, n/2 can be 2 if the code rounds down, and it can be 1 if the code rounds toward zero. This calculation works only if the code rounds toward zero. This allowance was changed recently for C and for C++, but I haven't been paying attention, and I don't remember which way the rounding goes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.