Thread: Largest prime factor...

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    17

    Largest prime factor...

    I am trying to solve some problems on Project Euler, and currently have very little experience with or knowledge about programming. I've learned up until while loops :P
    Anyways, I decided to see how many I can do before I have to move on and continue learning. This problem was the one I decided to stop after, as it took me a while to figure out:
    The prime factors of 13195 are 5, 7, 13 and 29.
    What is the largest prime factor of the number 600851475143 ?

    The problem here is that while writing the code, I had x variable assigned to 13195, so that I would know if it is working correctly depending on whether or not it displayed 29. Now, I am faced with the problem of 600851475143 being too large for an int variable. As a matter of fact, it's even too long for a long long int variable.
    However, I am somewhat opposed to the idea of just having someone do all the work for me (but honestly, I'm happy I made it this far with what little knowledge I have), so if upon reviewing the code you notice that I won't be able to actually make this code work without making drastic changes, than please tell me so and I will just leave this until later. Otherwise, I'm all ears
    *Please note another flaw, 2 is never considered as a prime number when you run this, but I ignored that for now because there will of course in this case be larger prime factors, so the answer should still be correct*

    Code:
    #include <stdio.h>
    int main(void)
    {
        int count = 2, countdiv = 2, x = 13195, div = 0, prime = 0; //count is to count till x (to find the factors), countdiv is to count till count (while checking if prime), div = divisor
        while(count < x) // This outer while loop is meant to find the factors of x
        {
            if (x % count == 0) // This actually checks if the counter is indeed a factor of x
            {
                div = count; // div (for divisor) is now the value of whichever integer is being checked
                countdiv = 2; // This is required, as you'll see further down to end the while loop I had to assign countdiv a higher value than div, and this resets it so that it can be used in following loops
                while(countdiv <= div) // *Check after code for info
                {
                    if(div % countdiv != 0){ // If it is a prime number SO FAR...
                        countdiv++;} // Check the next counter (ex : 5 % 2, prime so far, check 5 % 3, 5 % 4)
                    else{
                        countdiv += div;} // If it is NOT a prime number, than end the loop (make countdiv larger than div) and check the next factors
    
                    if(countdiv == div){ // If countdiv reaches the value of div, then the loop has not been ended, meaning div IS prime
                        prime = div; // Hmm, I wonder what this does?
                        printf("Prime: %d\n", prime);
                        }
                }
                count++; // Adds 1 to count if it is a factor of x, so that more prime factors can be found
            }
            else
                count++; // Adds 1 to count if it is NOT a factor of x, so that a factor CAN be found
        }
        printf("The largest prime factor of %d is:\n>%d\n", x, prime); // Outputs answer
        return 0;
    }
    Thanks in advance for any help!

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You either need to use a library that handles exceptionally large numbers, or you need to do all the conversion back and forth yourself using strings.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Feb 2011
    Posts
    17
    P.S - When I add long long to the start of the int line, and then run it, the output is:
    Prime: 71
    Prime: 839
    Prime: 1471
    Prime: 6857
    and then it just hangs there and does nothing

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    It's probably not that it's hanging. It's probably working on whatever the next number is. Add in some printf statements if you want to know for sure.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Feb 2011
    Posts
    17
    Quote Originally Posted by quzah View Post
    You either need to use a library that handles exceptionally large numbers, or you need to do all the conversion back and forth yourself using strings.
    Ahh, yes someone mentioned using a library to me. I'm not sure what you mean by doing the conversion between strings (as in character strings?), so I'll assume that it's too advanced for me at this point. However, do you know where I could find out what library to include (if I have to download it, maybe you could tell me where to find it?)

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    1. Find a search engine.
    2. Type these magic words: c large number library
    3. Locate the button labeled "Magic".
    4. Press it.


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Feb 2011
    Posts
    17
    Quote Originally Posted by quzah View Post
    It's probably not that it's hanging. It's probably working on whatever the next number is. Add in some printf statements if you want to know for sure.


    Quzah.
    I think you are right, added in a few printf's saying "About to check if this is a factor" and "about to check if factor is prime", and now it's just a blinking wall of text ^.^ Thanks for that, had I not known I wouldn't have thought to leave it open for so long. Now I know what to do when dealing with large numbers in the future. Cheers, and thanks for the incredibly quick replies btw.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You'll probably want to go ahead and take them back out now that you know it's not broken. It is going to slow it down a huge amount writing all of that over and over.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Feb 2011
    Posts
    17
    Quote Originally Posted by quzah View Post
    You'll probably want to go ahead and take them back out now that you know it's not broken. It is going to slow it down a huge amount writing all of that over and over.


    Quzah.
    Yes, I took out the ones that say "About to check if factor", and it's going much faster. I'll take out the other one as well though, I didn't realize they could slow it down so much. Thanks again

    Quote Originally Posted by quzah View Post
    1. Find a search engine.
    2. Type these magic words: c large number library
    3. Locate the button labeled "Magic".
    4. Press it.


    Quzah.
    I can't see any "Magic" button???
    Last edited by Opi8; 03-22-2011 at 05:07 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  2. last prime factor
    By frango9000 in forum C Programming
    Replies: 7
    Last Post: 07-27-2006, 12:42 PM
  3. Replies: 3
    Last Post: 03-29-2005, 04:24 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Prime Factor Fxn
    By alpha in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2003, 10:44 AM