integer constant is too large for type

Hi,
I'm trying to solve the problems at Project Euler (projecteuler.net). I think I've got the algorithm right but I'm restricted by the range of values an unsigned long long can take.
Here's the problem:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 317584931803?

Here's my code:

Code:

---

#include <iostream>

using std::cout;        using std::cin;
using std::endl;

int main()
{
        unsigned long long int num = 317584931803;
       
        unsigned long i;
        unsigned long primefactor;
        for (i=2; i <= num; i++)
        {
                if (num % i == 0)
                {
                        while (num % i == 0)
                                num /= i;
                        primefactor = i;
                }
        }
        cout << primefactor;

        return 0;
}

---

I even tried finding the smallest prime factor, dividing by it, and using the result. The smallest prime factor is 67. The result of the division is 4740073609, which is still too large for the type. I kept on trying to find another prime factor, but I reached 300 with no others.

Can anyone tip me onto the right track?

Make primefactor a long long as well.

When you initialize num, you can append the "LL" designation too:

Code:

---

unsigned long long int num = 317584931803LL ;

---

Todd

Make use of modulo arithmetic. Assuming a, b, and c are all positive, then .....

(a+b)%c = (a%c + b%c)%c

(a*b)%c = ((a%c)*(b%c))%c

Express num as 67*(a+b) ..... then you can do it using simple 32 bit long variables ....

Quote:

---

Originally Posted by Todd Burch

Make primefactor a long long as well.

When you initialize num, you can append the "LL" designation too:

Code:

---

unsigned long long int num = 317584931803LL ;

---

Todd

---

I tried it without appending the LL and it gave an error ? The compiler can't understand it is a long long by looking at the 12 digits and the data type of 'num' ?

Quote:

---

Originally Posted by abk

I tried it without appending the LL and it gave an error ? The compiler can't understand it is a long long by looking at the 12 digits and the data type of 'num' ?

---

I have to add the LL too with my compiler (gcc). I suspect the compiler assumes an INT when parsing unless told otherwise, just as it assumes double unless it's told the value is a float.

I guess the compiler is just dumb. Some compilers, such as Visual Studio, don't require any prefix at all.

Quote:

---

Originally Posted by Elysia

I guess the compiler is just dumb. Some compilers, such as Visual Studio, don't require any prefix at all.

---

I'm guessing the compiler has not yet determined the end result will be a long long. There is an assignment operator, which would probably trigger the compiler to evaluate the RVALUE expression first, and the default type for number constants is most likely INT.

Todd

317 584 931 803 is 49 F189 7BDB in hex, which is bigger than FFFF FFFF that a 32-bit integer can hold, so the compiler can effectively know it's a 64-bit integer in this case.

That is interesting. At the moment C++ does not have the long long built-in type, so this would be an extension (ported from C99 support, perhaps).

The C++ Standard section 2.13.1 is quite clear:

Quote:

---

The type of an integer literal depends on its form, value, and suffix. If it is decimal and has no suffix, it has the first of these types in which its value can be represented: int, long int; if the value cannot be represented as a long int, the behavior is undefined.

---

So, we are in the realm of undefined behaviour. It seems to me that MSVC is not wrong since its interpretation is consistent with the standard (it cannot be represented as an int, long int, ... ah but we support long long, so let's make it that). gcc also seems correct (this literal looks like a long long... but the Standard says that the behaviour is undefined, so let's require the user to use the LL prefix from C99, just to be sure that it is not a typographical error).

EDIT:
C99 section 6.4.4.1 states: "The type of an integer constant is the first of the corresponding list in which its value can be represented." It then goes on to list for integer literals with no suffix: int, long int, long long int.

It seems to me that reporting an error is wrong (but allowed, since this is in the realm of undefined behaviour). In C99 it would probably be wrong to even report a warning.