1

I build a program to find out the largest prime factor of 2^1000. It worked, and gave the right answers to my smaller test numbers, but then I realized that for my number I would have to use BigInteger. I've never used it before so I'm pretty sure I did something wrong. The BigInteger program doesn't give me back anything and doesn't finish running.

Here's the program, using primitive data types, that works: 

public class PE3 { public static void main(String[] args) {
  int num = 13195; 

  //find factors of 'num'
  for (int i=(num); i>2; i--) {
    if ((num%i)==0)
      testPrime(num, i); 
  }
 }

  // find if factor is prime
  public static void testPrime(int num, int i){
    for (int j=2; j<i; j++) {
      if ((i%j)==0) 
        break; 
      if (j==(i-1))
        System.out.println(i); 
}
  }}

Here's (what I think is) the same program using BigInteger: 

import java.math.BigInteger; 

public class PE3BI { public static void main(String[] args) {
  BigInteger num = new BigInteger("600851475143"); 
  BigInteger zero = new BigInteger("0"); 
  BigInteger one = new BigInteger("1"); 
  BigInteger two = new BigInteger("2"); 

  //find factors of 'num'
  for (BigInteger i = new BigInteger("600851475143"); i.compareTo(two)==1; i.subtract(one)) {
    if ((num.mod(i))==zero)
      testPrime(num, i, one, zero); 
  }
  }

  // find if factor is prime
  public static void testPrime (BigInteger num, BigInteger i, BigInteger one, BigInteger zero){
    for (BigInteger j = new BigInteger("2"); j.compareTo(i)==-1; j.subtract(one)) {
      if ((i.mod(j))==zero) 
        break; 
      if (j.compareTo(i.subtract(one))==0)
      {System.out.println(i); 
        System.exit(0); }
    }}}
microslayer
  • 155
  • 2
  • 3
  • 9
  • Use `i.equals(BigInteger.ZERO)` instead of == 0. Also, BigIntegers are immutable, j.subtract does nothing if you do not assign the value to something: j = j.subtract(one). – Adrian Leonhard Feb 17 '15 at 03:29
  • Also you probably want to do `j.add(one)` instead of `.subtract()` in the `for` loop in `testPrime()`. – augurar Feb 17 '15 at 03:31
  • And `BigInteger`s are immutable, the arithmetic methods return a new `BigInteger` of the result, they don't modify the original one. – augurar Feb 17 '15 at 03:33

3 Answers3

1

While, piotrek's answer will solve one of your problems, your program still won't work.

Need to do's:

  1. Don't use == for comparisons. It doesn't work for non-primitives, such as BigInteger(piotrek)
  2. i.subtract(one) as the last item in a loop does nothing. Use i = i.subtract(one) and the equivalent for j.

Would be good:

Although technically correct, a.compare(b) == -1 and a.compare(b) == +1 are typically not the best practice for code readability and it might not be the case that compare returns one of these three values in all situations, so don't get in the habit. Use a.compare(b) < 0 and a.compare(b) > 0 instead.

k_g
  • 4,333
  • 2
  • 25
  • 40
0

you can't do comparisons like object == zero. it works only for primitives. now, your numbers are objects so it checks if reference is the same. change it to compare or equals

piotrek
  • 13,982
  • 13
  • 79
  • 165
  • What would I do for something like `num.mod(i))==zero`? – microslayer Feb 17 '15 at 03:40
  • same answer. first you must compute your number. that `num.mod(i)`. later you have to compare it with `zero`. but not using `==` as it doesn't work for objects the way you expect. use equals or compare instead. this may help you http://stackoverflow.com/questions/767372/java-string-equals-versus – piotrek Feb 17 '15 at 13:08
0

It might be better to use a long instead of the BigInteger class?

I just made this using your code to check if a number is prime or not prime:

long num = 600851475143L; 

boolean prime = true;//Check this after for loop for prime.
for (long i=2; i<num; i++) {//Loops through all numbers between 2 and the number given to test.
    if ((num%i)==0){//This is true if number is not prime.
        prime = false;
        System.out.println("Not prime: " + i);
        break; 
    }
}
Forseth11
  • 13
  • 6