Win a copy of Mesos in Action this week in the Cloud/Virtualizaton 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: 20531
54
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: 48968
60
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: 48968
60
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: 3078
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: 48968
60
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: 48968
60