Thread: integer constant is too large for type

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    230

    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?
    I might not be a pro, but I'm usually right

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Make use of modulo arithmetic. Assuming a, b, and c are all positive, then .....

    (a+b)&#37;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 ....
    Last edited by grumpy; 02-09-2008 at 08:20 AM.

  4. #4
    Super unModrator
    Join Date
    Dec 2007
    Posts
    321
    Quote Originally Posted by Todd Burch View Post
    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' ?
    Last edited by abh!shek; 02-09-2008 at 08:42 AM.

  5. #5
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by abk View Post
    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.
    Mainframe assembler programmer by trade. C coder when I can.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I guess the compiler is just dumb. Some compilers, such as Visual Studio, don't require any prefix at all.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by Elysia View Post
    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
    Mainframe assembler programmer by trade. C coder when I can.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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:
    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.
    Last edited by laserlight; 02-09-2008 at 12:01 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Assignment HELP!!
    By cprogrammer22 in forum C Programming
    Replies: 35
    Last Post: 01-24-2009, 02:24 PM
  2. Replies: 7
    Last Post: 06-01-2008, 07:47 AM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  4. Very large signed integer math question
    By Criz in forum C Programming
    Replies: 8
    Last Post: 12-01-2002, 12:43 PM
  5. is there an infinitely large integer type?
    By MKashlev in forum C++ Programming
    Replies: 7
    Last Post: 08-10-2002, 02:31 PM