So this is problem 3 from project Euler. For those who don't know, I have to find out the largest prime factor of 600851475143. I have the below code:
import java.lang.Math;
// 600851475143
public class LargestPrimeFactor {
public static void main(String[] stuff) {
long num = getLong("What number do you want to analyse? ");
long[] primes = primeGenerator(num);
long result = 0;
for(int i = 0; i < primes.length; i++) {
boolean modulo2 = num % primes[i] == 0;
if(modulo2) {
result = primes[i];
}
}
System.out.println(result);
}
public static long[] primeGenerator(long limit) {
int aindex = 0;
long[] ps = new long[primeCount(limit)];
for(long i = 2; i < limit + 1; i++) {
if(primeCheck(i)) {
ps[aindex] = i;
aindex++;
}
}
return ps;
}
public static boolean primeCheck(long num) {
boolean r = false;
if(num == 2 || num == 3) {
return true;
}
else if(num == 1) {
return false;
}
for(long i = 2; i < Math.sqrt(num); i++) {
boolean modulo = num % i == 0;
if(modulo) {
r = false;
break;
}
else if(Math.sqrt(num) < i + 1 && !modulo) {
r = true;
break;
}
}
return r;
}
public static int primeCount(long limit) {
int count = 0;
if(limit == 1 || limit == 2) {
return 0;
}
for(long i = 2; i <= limit; i++) {
if(primeCheck(i)) {
count++;
}
}
return count;
}
public static long getLong(String prompt) {
System.out.print(prompt + " ");
long mrlong = input.nextLong();
input.nextLine();
return mrlong;
}
}
But when I test the program with something (a lot) smaller than 600851475143, like 100000000, then the program takes its time - in fact, 100000000 has taken 20 minutes so far and is still going. I've obviously got the wrong approach here (and yes, the program does work, I tried it out with smaller numbers). Can anyone suggest a less exhaustive way?
try this ..
public class LargestPrimeFactor{
public static int largestPrimeFactor(long number) {
int i;
for (i = 2; i <= number; i++) {
if (number % i == 0) {
number /= i;
i--;
}
}
return i;
}
/* change according to ur requirement.
public static long getLong(String prompt) {
System.out.print(prompt + " ");
long mrlong = input.nextLong();
input.nextLine();
return mrlong;
}
*/
public static void main(String[] args) {
//long num = getLong("What number do you want to analyse? ");
System.out.println(largestPrimeFactor(600851475143l));
}
}