My code finds the prime factorization of numbers, ordering the prime numbers from least to greatest. It prints a list of 999999 prime factorizations (which can be changed if you edit the function call in the main method). I'm thinking that maybe the string concatenation is the most expensive operation because Java Strings are immutable, meaning they must be destroyed and reconstructed every time their value is changed. I'm not quite sure how to connect strings without concatenation. I am also wondering if I am missing any optimizations with the math algorithm itself. Note that I am already aware that you only need to check up to the square root of a number for prime factors, that's in my code.
Thanks, here is my code (written in Java in the IDE Eclipse).
public class Prime {
public static void main (String [] args) {
factorList(999999);
}
public static boolean isPrime(int x) {
if (x == 1) return false;
for (int i = 2; i<= Math.sqrt(x); i++) {
if (x % i == 0 && i != x) {
return false;
}
}
return true;
}
public static int factor (int x) {
for (int i = 2; i<= Math.sqrt(x); i++) {
if (x % i == 0 && i != x) {
return i;
}
}
return -1;
}
public static void factorList (int x) {
if (x<=1) {
throw new IllegalArgumentException("1 & negative numbers are neither prime nor composite");
}
for (int i = 2; i<= x; i++) {
if (isPrime(i)) {
System.out.println(i +" is a prime number, can't be factored");
} else {
System.out.println(i+ " is a composite number: " + factor(i) + " * " + (i/factor(i)));
}
}
}
public static void factorList (int [] x) {
for (int i = 0; i< x.length; i++) {
if (isPrime(x[i])) {
System.out.println(x[i] +" is a prime number, can't be factored");
} else {
System.out.println(x[i]+ " is a composite number: " + factor(x[i]) + " * " + (x[i]/factor(x[i])));
}
}
}
public static void primeFactorize (int x) {
if (isPrime(x)) {
System.out.print(x);
} else {
System.out.print(factor(x)+ "*");
primeFactorize(x/factor(x));
}
}
}