I am coding a program to factor a number into is prime factors. The program works as follows:
1) Input a number that you wish to factor (I will refer to is as "inputNumber")
2) Test to see if you can divide inputNumber by 2,3,5 and 7 (first 4 prime numbers). if you can divide by any of these, then do so as many times as you can (i.e. 12 can be divided by 2 twice, after this, there is a remainder of 3) note every time I divide by a number, I store that number in an array list and I keep the remainder for further testing
3) Starting with i=11 (the next prime number) in a while loop, I do the following:
while (i < remainder+1) {
divides by i? yes: store i,
repeat until you cant divide by i. i=i+2,
divides by i? yes: store i, repeat until you can't divide by i.
i=i+4, same as before... i=i+2...
and finally stop the loop at i=i+2
}
this way, every successful iteration of the while loop will divide the remainder by numbers finishing by 1,3,7,9. We do not need to test even numbers since we divided by 2 already, nor do we need to test the ones ending by 5 since we already divided by 5. In the end, we
This is a very neat algorithm since it its much much faster than factoring a number by testing one number after the other, in fact, you only need to test 40% of all numbers.
My question is: When I tried factoring 84738329279, a number picked randomly, it omits to put the last prime factor in the list, I can't quite figure this out. the only factors that show up are 41, 61 and 61. Can someone help me find what I'm doing wrong? here is my code:
import java.util.Scanner;
import java.math.BigInteger;
public class Test {
public static void main(String[] args) {
// create a scanner object for inputs
Scanner in = new Scanner(System.in);
// prompt user for number to factor
System.out.print("enter a number to factor: ");
String digits = in.next();
BigInteger BigDigits = new BigInteger(digits);
BigInteger[] results = factor.factorThis(BigDigits);
System.out.print("Factors are ");
for (int i=0; i<results.length;i++){
System.out.print(results[i] + " ");
}
System.out.println("");
}
}
import java.util.ArrayList;
import java.math.BigInteger;
public class factor {
// Returns the prime factors of the BigInteger number
public static BigInteger[] factorThis(BigInteger number) {
BigInteger i = new BigInteger("11");
ArrayList<BigInteger> divisors = new ArrayList<BigInteger>(0);
BigInteger[] firstPrimes = new BigInteger[4];
firstPrimes[0] = new BigInteger("2");
firstPrimes[1] = new BigInteger("3");
firstPrimes[2] = new BigInteger("5");
firstPrimes[3] = new BigInteger("7");
// loop that test for first 4 prime numbers
for (int l=0;l<4;l++){
while ((number.mod(firstPrimes[l])).compareTo(BigInteger.ZERO) == 0) {
number = number.divide(firstPrimes[l]);
divisors.add(firstPrimes[l]);
}
}
// loop that factors only numbers finishing by 1,3,7,9
while (i.compareTo(number) == -1){
// check for ending by 1
if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
number = number.divide(i);
divisors.add(i);
}
}
else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
i=i.add(firstPrimes[0]);
}
// check for ending by 3
if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
number = number.divide(i);
divisors.add(i);
}
}
else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
i=i.add(firstPrimes[0].multiply(firstPrimes[0]));
}
//check for ending by 7
if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
number = number.divide(i);
divisors.add(i);
}
}
else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
i=i.add(firstPrimes[0]);
}
// check for ending by 9
if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
number = number.divide(i);
divisors.add(i);
}
}
else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
i=i.add(firstPrimes[0]);
}
}
// store prime factors into a BigInt array
String[] strArrayDivisors = divisors.toString().replaceAll("\\[", "").replaceAll("\\]","").replaceAll("\\s","").split(",");
BigInteger[] BigIntDivisors = new BigInteger[strArrayDivisors.length];
for(int j=0;j<strArrayDivisors.length;j++){
BigIntDivisors[j] = new BigInteger(strArrayDivisors[j]);
}
// returns all factors of "number"
return BigIntDivisors;
}
}
Thanks in advance.