# Prime Factor

Pawan Arora

Ranch Hand

Posts: 105

posted 8 years ago

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

Thanks in advance for help.

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.

posted 8 years ago

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.

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 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago

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

Posts: 103

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

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.

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: 50770

83

posted 8 years ago

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.

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

Posts: 103

Campbell Ritchie

Sheriff

Posts: 50770

83

posted 8 years ago

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 thatPrint 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.}

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

posted 8 years ago

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 ]

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

Posts: 3090

14

posted 8 years ago

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.

The thing to realize is that once you have extracted all the prime factors which are <= Math.sqrt(n), any remaining quotient

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

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]: 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: 50770

83

posted 8 years ago

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.

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

Posts: 103

Campbell Ritchie

Sheriff

Posts: 50770

83

posted 8 years ago

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.

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.Originally posted by Anoobkumar Padmanabhan:

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

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.