Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Prime Factor

Pawan Arora
Ranch Hand
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.

Rob Spoor
Sheriff
Posts: 20665
65
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.

Garrett Rowe
Ranch Hand
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.

Ranch Hand
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.

Garrett Rowe
Ranch Hand
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
Posts: 50211
79
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.

Ranch Hand
Posts: 103
Hi Pawan

Shall we try with the following code?

Campbell Ritchie
Sheriff
Posts: 50211
79
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
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 ]

Mike Simmons
Ranch Hand
Posts: 3090
14
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
Posts: 50211
79
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.

Ranch Hand
Posts: 103
Hi

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

Campbell Ritchie
Sheriff
Posts: 50211
79
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.

 Consider Paul's rocket mass heater.