Prime Factor

[Pawan Arora]

I want to develop a program to evaluate the prime factor of any particular number, here I've done a bit work on it

class Prime_Factor
{
public void method1()
{int s;
System.out.println("The prime factor for the numbers ");
for(int i=2;i<100;i++)
{
if(jackass(i)==true)
{
 
int l=12;
s=l/i;
System.out.println("The prime factor number is "+s);
 
}
}
}
 
public boolean method2(int l)
{
if(l==2)
{
return true;
}
if(l%2==0)
{
return false;
}
for(int i=3;i<l;i+=2)
{
if(l%i==0)
{
return false;
}
}
 
return true;
}
public static void main(String[] args)
{
Prime_Factor a=new Prime_Factor();
a.method1();
}
}

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]

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:

int l = 12;
for (int i = 2; i <= 12; i++)
{
    if (method2(i))
    {
        s = l / i;
        System.out.println("The prime factor number is " + s);
    }
}

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]

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.

[Anoobkumar Padmanabhan]

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]

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]

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]

Hi Pawan

Shall we try with the following code?

  
public class PrimeFactor {
public static void main(String[] args) {
 
int number = 57; // input the number here
 
int f1 = 2;
while (f1 < Math.sqrt(number)) {
if (number % f1 == 0) {
int f2 = number / f1;
printIfPrime(f1);
if (f1 != f2) {
printIfPrime(f2);
}
}
f1++;
}
}
 
private static void printIfPrime(int factor) {
for (int i = 2; i <= Math.sqrt(factor); ++i) {
if (factor % i == 0) {
return;
}
}
System.out.print(factor + " ");
}
}

[Campbell Ritchie]

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]

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]

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]

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]

Hi

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

  public class PrimeFactor {
public static void main(String[] args) {
 
int number = 135; // input the number here
 
int f1 = 2;
while (f1 <= number) {
if (number % f1 == 0) {
number = number / f1;
printIfPrime(f1);
f1 = 2;
} else {
f1++;
}
}
}
 
private static void printIfPrime(int factor) {
for (int i = 2; i <= Math.sqrt(factor); ++i) {
if (factor % i == 0) {
return;
}
}
System.out.print(factor + " ");
}
}
  

[Campbell Ritchie]

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.