aspose file tools*
The moose likes Java in General and the fly likes Finding the largest Prime Factor Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Finding the largest Prime Factor" Watch "Finding the largest Prime Factor" New topic
Author

Finding the largest Prime Factor

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89
Im trying to solve this problem
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


My code is this:


I think this code will work but it will take FOREVER to work, I waited about an hour and got no results...
anyone have any alternative code or any idea to get the right answer?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Welcome to the Ranch.

Please check the JavaRanch naming policy and change your displayed name to conform.

I shall have a look at your code and see whether I can make anything of it. It ought to produce the highest prime factor in a few milliseconds.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Take a number n.
Start with n = 2.
while the remainder is > n
if the number divides exactly by n
divide the number by n
else
increase n by 1
end while
print result

The problem you have is that you are repeatedly checking whether the number is prime, and also counting donw; it creates exponential complexity. Once you get above maybe 20 digits, factorisation always becomes a very slow process.
Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89


this is taking so long too...
Is this what you want?
by the way, where can I find the naming policy?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Since the number is less than 19 digits long, I tried it with longs rather than BigIntegers. It found the largest prime factor (at least I think it did) in <1 second. Try changing to long. Remember that any factorisation algorithm is prone to exponential complexity and the time to solve it increases proportionally to 2^n where n is how many digits the number has.


The naming policy is explained here.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18834
    
  40

by the way, where can I find the naming policy?


naming policy


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
The problem is the condition for the while loop. There is a subtle mistake in that line which converts the condition to a tautology. I copied and pasted your code, corrected the error and added some calls to System.currentTimeMillis(). It took 37 ms.

Changing your number to 132456600851475143 lengthened the running time to 6.5 seconds, and changing to 1324567600851475143 made it take over � hour and I stopped it with ctrl-C. I told you it would take much longer if you lengthen the number; there was an article in Scientific American either this month or last month about quantum computing. Read that; it says more about how long it can take to factorise big numbers.

I shall leave you to find the error; read the line starting which very carefully. I think there are two things you have to alter. If you can't find it by tomorrow I shall try some hints. Good luck.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
This problem comes from Project Euler a pretty cool site. I only know because I just solved it about a week ago. One thing you should know is that Project Euler problems build upon themselves, so once you get to Problem 7 and especially Problem 10, even the solution you have now is going to take a good bit of time. My suggestion would be to read to google "sieve of eratosthenes", you'll find a useful algorithm for for building a list of prime numbers. Good luck.

FWIW, I'm currently stuck trying to figure out an algorithm for Problem 18. I think I'll be starting a topic in the Programming Diversions forum soliciting a little help...


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89
@Campbell Ritchie

gives me The literal 600851475143 of type int is out of range...

@Garrett Rowe, I solved problems 7 and 10 long time ago, i just cant seem to solve this one :S

@Campbell Ritchie, are you talking about the first code or the second code, and could you please hint or give me more explanation about the error I made? please...

thanks all
Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89
Fixed the name thing btw
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Thank you for correcting your name.

Garrett Rowe is right that I have provided a very simple solution; the sieve of Eratosthenes will provide a list of prime numbers starting from 2.
Unfortunately if you are factorising an 18-digit number you might in theory have a factor which has 9 digits in; you would require an array with 1000000000 members to represent all 9-or-fewer-digit numbers and you are risking running out of memory.

As I said, all factorising solutions run the risk of going into exponential complexity, so they tend to take ages to run. Once you get beyond 50 digits in decimal you are liable to find a program might take millions of years to produce a result. You can improve the algorithm by stopping divisions when you reach the square root of the original number; if you haven't found the largest prime factor by then, whatever remains is the answer.

Try changing "long a = 600851475143;" to "long a = 600851475143L;" If you miss the L out you are implying that the number literal is an int, which can't take 12 digits.

I was talking about the 2nd lot of code; there are two significant errors, both in the condition for the while loop.
  • You are testing the remainder (what in contintental Europe they call modulus).
  • You are testing whether it is smaller, whereas you actually want to test for being larger.
  • If you correct both those errors your app should run nicely.
    Garrett Rowe
    Ranch Hand

    Joined: Jan 17, 2006
    Posts: 1296
    Campbell: Unfortunately if you are factorising an 18-digit number you might in theory have a factor which has 9 digits in; you would require an array with 1000000000 members to represent all 9-or-fewer-digit numbers and you are risking running out of memory.

    Actually that depends on your implementation strategy. You don't need to use an array at all.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38818
        
      23
    Thank you. How do you do it? I only know how to implement the Sieve of Eratosthenes with an array.
    Garrett Rowe
    Ranch Hand

    Joined: Jan 17, 2006
    Posts: 1296
    Here's an implementation that doesn't use an array. Instead it stores the next few non-prime numbers in a Map, if the number isn't in the Map, when the sieve "gets to it" then the number is prime.
    To be fair to your earlier comment, you aren't likely to generate any nine digit primes with this sieve either. It slows waaaay down after about the 250,000th prime.
    \
    [ March 22, 2008: Message edited by: Garrett Rowe ]
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38818
        
      23
    Thank you, Garrett. I shall have to look at that method later. Does it still require a lot of memory to maintain a collection of prime numbers?

    Sam, have you solved the largest prime problem yet?
    Garrett Rowe
    Ranch Hand

    Joined: Jan 17, 2006
    Posts: 1296
    Originally posted by Campbell Ritchie:
    Does it still require a lot of memory to maintain a collection of prime numbers?


    The class doesn't really maintain a collection of primes, it actually maintains a collection of the next few non primes, and generates the next prime based on the next number that's not in the collection. That being said, as numbers get larger the distance between primes gets larger and therefore there are more non primes maintained in the Map. I haven't profiled it, but I would guess its pretty inefficient for very large numbers.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38818
        
      23
    Yes, I can more-or-less see how it works. It would work well for a single run where you are trying to factorise a single number, but for repeated runs an array would be more economical on time albeit expensive on memory.

    And of course you can get all the primes under 1000000 for 1000 passes through an array; you only have to go as far as the square root of the largest number.

    And Sam, have you got the algorithm to work?
    Sam Benry
    Ranch Hand

    Joined: Mar 21, 2008
    Posts: 89
    I still dont get my errors,
    you said
    while the remainder is > n

    so I wrote


    but with this code, the while loop is never executed, but when I change it to

    the program starts working...

    but it never stops working...
    still unable to work it out
    here is what im trying
    Paul Clapham
    Bartender

    Joined: Oct 14, 2005
    Posts: 18570
        
        8

    That's because "num % i" always returns a number between 0 and i-1. So "num % i < i" is always going to be true. So your loop never ends.

    Therefore, that isn't the correct stopping condition. If you explain the algorithm to yourself out loud, you should be able to figure out what the correct condition is.
    Patrick Loz
    Greenhorn

    Joined: Dec 21, 2007
    Posts: 5
    Originally posted by Garrett Rowe:
    This problem comes from Project Euler a pretty cool site. I only know because I just solved it about a week ago. One thing you should know is that Project Euler problems build upon themselves, so once you get to Problem 7 and especially Problem 10, even the solution you have now is going to take a good bit of time. My suggestion would be to read to google "sieve of eratosthenes", you'll find a useful algorithm for for building a list of prime numbers. Good luck.

    FWIW, I'm currently stuck trying to figure out an algorithm for Problem 18. I think I'll be starting a topic in the Programming Diversions forum soliciting a little help...


    Awesome site! The first I've seen of it... Tons of fun problems...
    Sam Benry
    Ranch Hand

    Joined: Mar 21, 2008
    Posts: 89
    ok solved it, in less than a sec


    thanks everybody for your help
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38818
        
      23
    Not convinced.

    You ought to test while(i < num) and forget about the % operator.
    Bill Shirley
    Ranch Hand

    Joined: Nov 08, 2007
    Posts: 457
    The fact that prime factorization blows up is what makes public key encryption so secure. You take two huge prime numbers (easy to find a prime), multiply them (easy), and provide the larger number publicly (factoring it is not feasible).

    details slightly more complicated,
    wikipedia.org - RSA


    Bill Shirley - bshirley - frazerbilt.com
    if (Posts < 30) you.read( JavaRanchFAQ);
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Finding the largest Prime Factor