File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Prime Factor Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Prime Factor" Watch "Prime Factor" New topic
Author

Prime Factor

Pawan Arora
Ranch Hand

Joined: Sep 14, 2008
Posts: 105
I want to develop a program to evaluate the prime factor of any particular number, here I've done a bit work on it

here, I try to evaluate the prime factor of the number 12, but it's giving me an output like 6,4,2,1,1,0000.... what the problem this programme has? how can I tackle it? please give me a hint not the solution of this question.
Thanks in advance for help.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19794
    
  20

You are checking all prime numbers from 2 until 99. There are several that are larger than 12; 13 is one for instance.

For those, 12 / i will be 0 - since i > 12.

If you change your code to this:

You will at least stop at 12.

Now your code still is not correct. For instance, where is 3? That certainly is a prime factor. And 4 most definitely isn't.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
One straightforward solution to this problem is to list all of the primes less than or equal to (n / 2), where n is the number you are interested in factoring, and then iterate through them and figure out which ones are factors of n. To get the list of primes you can use a Sieve of Eratosthenes.


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

Joined: Aug 08, 2007
Posts: 103
Hi Rowe

shall we restrict the search in the set of primes less than or equal to squre root of n, where n is the number?

I think there is no need for searching till n/2.


Thanks<br /> <br />Anoobkumar<br />SCJP 1.5
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
For the algorithm I suggested restricting the list of primes to the square root of n is only sufficient if n is a perfect square.

For example if n = 10, the prime factors are {2, 5}, however the square root of 10 is 3.16227..., if you restricted the list of primes to those less than the square root of 10, then 5 would be missed.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40064
    
  28
Yes, I see what you mean. For the sieve of Eratosthenes, however, you can start from 2 and go up to i<=sqrt(x).
If you start from 2 and try dividing, you end up with a quotient; 2 < sqrt(10) and 10 / 2 = 5 and if 5 is prime you have the other factor.
On the other hand 2 < sqrt(12) but 12 / 2 doesn't give a prime number.
Anoobkumar Padmanabhan
Ranch Hand

Joined: Aug 08, 2007
Posts: 103
Hi Pawan

Shall we try with the following code?

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40064
    
  28
Have you been told that your input will be numbers with at most two prime factors? I think you need some way to list the factors, and I can think of three ways to do that
  • Print them on screen; for 12 you should get 2 2 3
  • Put them in a List<Integer>; for 12 it would contain 2 2 3.
  • Put them in a Map<Integer, Integer> where the "Key" represents the factor and the "Value" how many times it is used: 12 would come out to 2|-->2, 3|-->1.
  • I think you need to go through a Sieve of Eratosthenes algorithm and empty a boolean array of its composite numbers.
    primes[0]=false
    primes[1]=false
    primes[2]=true
    primes[3]=true
    primes[4]=false etc etc.
    Then you go through your numbers, if (primes[i]) {see whether that divides into your number, then record it and divide, otherwise try the next number.}
    Bill Shirley
    Ranch Hand

    Joined: Nov 08, 2007
    Posts: 457
    It's useful to note, you don't need to test for primeness to find the prime factors,

    if a number (ex 42) is say divisible by 6, you will hit 2 and 3 and remove them from the pool of options before you get to 6, mod by 6 will be on the remainder (7) will be false, (it's a useless test, as is all other even numbers, but modulo integer arithmetic is very quick)
    [ October 20, 2008: Message edited by: Bill Shirley ]

    Bill Shirley - bshirley - frazerbilt.com
    if (Posts < 30) you.read( JavaRanchFAQ);
    Mike Simmons
    Ranch Hand

    Joined: Mar 05, 2008
    Posts: 3018
        
      10
    The sieve of Eratosthenes is an algorithm for finding a list of prime numbers; it does not cover finding all the prime factors of a number. However, the idea of not needing to test factors > sqrt(n) is useful well beyond the sieve of Eratosthenes, just as Anoobkumar suggested.

    [Campbell]: If you start from 2 and try dividing, you end up with a quotient; 2 < sqrt(10) and 10 / 2 = 5 and if 5 is prime you have the other factor.

    The thing to realize is that once you have extracted all the prime factors which are <= Math.sqrt(n), any remaining quotient must be prime. So there's no need to wonder "if 5 is prime" - 5 must be prime, because all lower factors are guaranteed to have been extracted at this point.

    As a more detailed example, let's try factoring 234. Note that sqrt(234) is 15.something, so you will never need to try any factors higher than 15.

    Try dividing 234 by 2: the remainder is 0, so 2 is a factor, and the quotient is 117. Note that sqrt(117) is 10.something, so you will never need to try any factors higher than 10.

    Try dividing 117 by 2: the remainder is 1, so 2 is not a factor (any more). Move on.

    Try dividing 117 by 3: the remainder is 0, so 3 is a factor, and the quotient is 39. Note that sqrt(39) is 6.something, so you will never need to try any factors higher than 6.

    Try dividing 39 by 3: the remainder is 0, so 3 is a factor (again), and the quotient is 13. Note that sqrt(13) is 3.something, so you will never need to try any factors higher than 3.

    Try dividing 13 by 3: the remainder is 1, so 3 is not a factor any more.

    We have now tested all factors <= sqrt(13), where 13 was the more recent quotient. At this point we are guaranteed that 13 must be prime, because it could not possibly have any factors > sqrt(13) unless it had another factor < sqrt(13). And we know we've already extracted every factor <= 3, including one that occurred twice (3). So the remaining quotient of 13 must be prime. Even though 13 < sqrt(234) (the original number we were trying to factor), we know that 4 > sqrt(13), where that last 13 was the most recent quotient we were trying to factor. Once we've extracted all factors <= sqrt(q), where q is the most recent quotient, any quotient remaining after that must be prime.

    Important points in the above example:

    1. Every time you find one factor, the problem becomes easier, because now you just have to find factors of the latest quotient. After you find that 2 is a factor of 234, you no longer need to factor 234; you need to factor 117. After you find that 3 is a factor of 117, you no longer need to factor 117; you need to factor 39. After you find that 3 is again a factor of 39, you no longer need to factor 39; you need to factor 13. After every small success, the problem becomes simpler.

    2. Don't forget to keep extracting each factor repeatedly until you fail - some factors occur more than once. Like 3, in the above example.

    Also I would note that it's often impractical to keep taking sqrt() of new quotients, as sqrt() can be a time-consuming operation. It may be faster to test if newFactor * newFactor <= currentQuotient. A single multiplication is much faster than a sqrt().
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40064
        
      28
    I think we are in agreement here, Mike ; when I said "wonder whether 5 is prime," I was hoping people would realise that 5 is prime. I just didn't put it clearly.
    You are correct that when you have extracted all factors <= sqrt(i) whatever remains is the final prime factor. And that you have to repeat factors; as I said 12's factors are 2 2 3.
    And Bill Shirley correct that you don't need to test whether a potential factor is prime; if you have got rid of all 2s it will simply return false when you try 4 so you will go on to try 5.
    Anoobkumar Padmanabhan
    Ranch Hand

    Joined: Aug 08, 2007
    Posts: 103
    Hi

    Just look at this program. will this satisfies the issues?

    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40064
        
      28
    Originally posted by Anoobkumar Padmanabhan:
    Just look at this program. will this satisfies the issues?
    No. You haven't been following the discussion. We have already concluded that you don't actually need to check whether a factor is prime, to the printPrime method can be replaced by a print call. And reverting to a value of 2 is unnecessary.

    Many of us (see the Ranch style suggestions), myself included, think using "return" in the middle of a method is bad form. Many other people disagree.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Prime Factor