Recursion-Prime factors

[Arjunkumar Shastry]

Generally we don't use recursion unless its must as debugging recursive code takes time.I was thinking about the method which should return the prime factors of a natural number.For 100,it will be 2,2,5,5.Recursion is a natural choice as we find the factors similarly on a paper.

 
public static boolean isPrime(int n)
{
//return true if n is prime.
boolean ISPrime = true;
int sqrt = (int)Math.sqrt(n);
for(int i=2;i<=sqrt;i++)
{
  if(n%i==0)
   ISPrime = false;
}
return ISPrime;
}
 
 

 
public static ArrayList printFactors(int n)
{
if(isPrime(n) )
{
System.out.println(n);
}
else
{
   for(int i=2;i<=(n/2);i++)
{
if(n%i == 0 && isPrime(i))
  {
                     System.out.println(i);
     factors = printFactors(n/i);
      break;
   }

}//end of for.
}
   }//end of method

Now in this recursive method I want to return the factors,it has found out for number n,Any idea how to do this?

[Stan James]

Your method says it returns an ArrayList but it doesn't yet. Let's change it to modify an ArrayList instead:

void findPrimeFactors( List list, int n)

When you call yourself recursively pass the list along. When you print, also add the factor to the list. When it's all done the list will contain the same factors you printed.

[Ryan McGuire]

The most obvious way, as Stan pointed out, would be to pass the List/ArrayList (in addition to the reduced number) into the recursive so that each factor can be added as it's found.

Is there a way to get around this? How about this:
Have the method instantiate the ArrayList iff the number that was passed in is prime. Then it can just return the ArrayList and each instance of the method can add its factor to the ArrayList on the way out (i.e. between the recursive call and returing). One advantage to this is that the client object doesn't have to be responsible for instantiating the ArrayList.

I haven't tried running or even compiling this code, but...

public static ArrayList printFactors(int n) {
    ArrayList al == null;
 
    if (isPrime(n)) {
        al = new ArrayList();
        al.add(new Integer(n));
        System.out.println(n);
    }
    for (int i=2; i<=(n/2); i++) {
        if (n%i == 0) {
            ArrayList al = printFactors(n/i);
            al.add(new Integer(i));
            System.out.println(i);
            break;
        }
    }
    return al;
}

(You don't need the isPrime() call with the n%i test, because if i wasn't prime then a factor of i would have caused the loop to terminate in an earlier iteration.

Speaking of isPrime(), I wouldn't use that in printFactors() because of the repeated use of the for loop in the two methods. I'd just use the for(int i...) loop to determine primality (primeness? primularity? primosity?) in printFactors() and act accordingly (either instantiate the ArrayList or make the recursive call). Taking it even farther, I'd make public a static ArrayList getFactors(int n) as one method. Then, if needed isPrime() for other reasons, have isPrime(int n) call getFactors(n) to (silently) get the factors and return true iff the returned ArrayList has a size() == 1. Then have a third method printFactors(int n) that calls getFactors(n) and then prints the returned elements of the returned ArrayList.

But that's just me.

Ryan
[ April 07, 2005: Message edited by: Ryan McGuire ]

[M Beck]

why should debugging recursive code take any more time than debugging iterative code? is it perhaps because you're just not as familiar with recursive code? there's a good cure for that: get familiar with it!

the suggestions in this thread seem good. another suggestion: often it's a good idea to have a "core" method that's doing the actual recursing, perhaps passing along a collection (or some other variable) for accumulating the results as they're found. then have a "driver" method that gets the recursor started, passing in an empty collection (or whatever) as a way of saying "you haven't found any results yet". when the recursor finally returns its results, typically the "driver" would just pass these along to whatever method called it - to the rest of the world your "driver" is the whole method, and the recursor can be kept private.

this way the list of parameters to the recursor can be made "messy", to include whatever is needed in the recursion, but the list of parameters and return values for the "driver" can be kept neat for general use.

[Tom Blough]

While the Sieve of Erastosthenes is much faster for factoring small values of primes (up to Integer.MAX_VALUE), you can speed your code up quite a bit. You are alreadying testing up to n^0.5, but once you begin identifying the prime factors, you only need to check by using the found primes as divisors.

You'll agree that once you've determined that the number is divisible by 2, then there is not need to check 4, 6, 8.... Simililary, once 3 is determnied to be a prime factor, there is no need to check 6, 9, 12....

So therefore if I want to find the prime factors of 100, I only need to check the known primes of less than 100^0.5 or 2, 3, 5, 7. If 100 was not divisible by 2, 3, 5, or 7, then it would be prime.

Cheers,

[Stan James]

Ryan and M Beck are both right - I did a sloppy thing making the client pass in the list. In real life I'd make a public method that creates the list, calls the signature I showed on a private recursive method, then returns the list. I seem to do this fairly often becuase the recursive method needs some information like recursion depth to format a nice outline or something.

[James Carman]

To understand recursion, you must first understand recursion.

[Arjunkumar Shastry]

Thanks guys.It worked.I was unaware that Integer.MAX_VALUE is a prime number.

[David Harkness]

Originally posted by Arjunkumar Shastry:
I was unaware that Integer.MAX_VALUE is a prime number.

If I remember correctly from about 16 years ago, (2^n - 1) is often a prime number: 3, 7, 31, 127 (?). Since Integer.MAX_VALUE is (2^31 - 1), it stands a decent chance of being prime.

Note: I didn't check any of my math, and it's very late.

[Arjunkumar Shastry]

I just dded little code to test how many are primes are of form 2^n -1
1 true
3 true
7 true
15 false
31 true
63 false
127 true
255 false
511 false
1023 false
2047 false
4095 false
8191 true
16383 false
32767 false
65535 false
131071 true
262143 false
524287 true
1048575 false
2097151 false
4194303 false
8388607 false
16777215 false
33554431 false
67108863 false
134217727 false
268435455 false
536870911 false
1073741823 false
2147483647 true
Outof 31,only 9 are primes ! Unfair

[Arjunkumar Shastry]

It seems like when n is prime,2^n -1 is also prime.
Thanks