Thread: Calculating prime factor of a huge number.

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    22

    Calculating prime factor of a huge number.

    I've succesfully written some code that prints out the prime factors of integers. It works succesfully for small-ish integers, but my task is to calculate the largest prime factors of 600851475143. Here is my code, which works for the number 13195.

    Code:
    #include <stdio.h>
    
    int isprime (int n);    
    
    int main()
    {
        int prime;
        int i;
            for (prime = 5; prime < 75; prime ++){
           if (isprime(prime)&&13195%prime==0){
              printf("A prime factor is %d.\n", prime);
           }
        }    
        getchar();
        return 0;
    }   
    
    int isprime (int n)
    {
        int i;
        int boolean = 1;
        
        for (i = 2; i < n/2; i++){
            if (n%i==0){
               boolean = 0;
            }
        }
        return boolean;
    }
    Simply replacing the '13195' on line 10 with the huge integer 600851475143 doesn't work, as C doesn't like integers that big. I did a bit of research on how to represent numbers that large. I tried to represent it as a constant of type 'double' using:

    Code:
    #include <cmath>
    double f = 6.00851475143*pow(10.0,11.0);
    but that didn't work because of type differences, and it also failed when I typecasted f as an integer (it produced a large negative integer).

    So is there any way to represent this huge integer that works, or must I find another method to work out the largest prime factor? I certainly can't think of another method

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Depending on what compiler you are using, you may be limited to 32-bit unsigned, which is a shade over 4000000000. If your computer supports 64-bit integers, then you can get MUCH larger numbers. Microsoft compilers have a "_int64" type, whilst gcc uses the more standard form of "long long int".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    22
    I tried:

    Code:
    __int64 f = 600851475143;
    I get a compiler error saying 'integer constant is too large for "long" type'. Same for long long int.

    I'm using Dev-C++, I assume that int64 and long long int aren't supported on this compiler?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Bakster View Post
    I tried:

    Code:
    __int64 f = 600851475143;
    I get a compiler error saying 'integer constant is too large for "long" type'. Same for long long int.

    I'm using Dev-C++, I assume that int64 and long long int aren't supported on this compiler?
    They are, but you need to post-fix the number with LL to make it a "long long"(since it's a GCC based compiler, long long is fine, but you need to use "%I64d" to let printf display the number).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    22
    Quote Originally Posted by matsp View Post
    They are, but you need to post-fix the number with LL to make it a "long long"(since it's a GCC based compiler, long long is fine, but you need to use "%I64d" to let printf display the number).

    --
    Mats
    It works now, thanks a lot

  6. #6
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...
    Last edited by neandrake; 01-29-2009 at 06:54 PM.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  7. #7
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by neandrake View Post
    Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...
    You need a more powerful computer, like this one

    http://cgi.ebay.co.uk/TWO-OLD-RULER-...3A2|240%3A1318

    And one of these:-

    http://cgi.ebay.co.uk/Maths-Basics-A...3A2|240%3A1318

  8. #8
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by neandrake View Post
    Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...
    I think basicaly you will have to print the numbers into strings, which can be as long as you like and then impliment a routine to do long hand division, particularly if the denominator is greater than max_int. If it is less than max_int then you can probably use a faster method using 'normal' computer division, however I am not sure if you can get the correct remainder with that. I don't think you can 'split' the denomminator into a shorter numbers, at least I can't think of how to do it, maybe there is a method.

    I would expect there must be rountines done to do such 'stuff' already written.

  9. #9
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    Plenty of languages other than C support arbitrary precision arithmetic natively, and project euler doesn't require the use of C. If you need/want to use C and don't have C99 long long support (you don't necessarily need a 64 bit machine), there's always libgmp (The GNU MP Bignum Library).
    Last edited by cwr; 01-29-2009 at 11:10 PM. Reason: Clarification

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You can use digits in int arrays, you just have to know your base 10 number line, and how it works.

  11. #11
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    esbo - lol ;p

    cwr - or you can write your own library (which was my point). I am actually working on a personal C library to store 8 digits inside of a 32-bit integer. I have it working, but have been too lazy to implement arithmetic functions for actually using them. Some day I will get around to it. Thank you for bringing up my point.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  12. #12
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    A good bignum library actually doesn't use strings to represent numbers. I once had to write a bignum library in ML. I used an array of ints to store the digits of a number in a large base, say sqrt(INT_MAX). This way, you can use ordinary arithmetics on digits (and probably won't use many digits... every int value fits into two digits this way). The string part is only needed to convert the number from and to a human readable form.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  13. #13
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Snafuist - Curious, how are you storing numbers in base sqrt(INT_MAX)?
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Snafuist
    how are you storing numbers in base sqrt(INT_MAX)?
    It was stated in the earlier part of the sentence: "an array of ints".
    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

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Or if the question is "INT_MAX" isn't a perfect square, that is true; presumably the base was 2^(n/2) if int had n bits in it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Number Guessing
    By blacknapalm in forum C Programming
    Replies: 2
    Last Post: 10-01-2008, 01:48 AM
  2. Problem running prime number test.
    By galactic_ronin in forum C++ Programming
    Replies: 25
    Last Post: 02-20-2008, 12:21 PM
  3. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  4. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM
  5. How is to check prime number?
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-04-2001, 11:36 PM