最大的素因子程序采用aaaages-Java

Question

这就是Euler项目的问题3。对于那些不知道的人，我必须找出最大的素因子600851475143。我有以下代码：

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;
}
}

但是，当我用比600851475143小（很多）的东西测试程序时，比如100000000，那么程序需要时间——事实上，100000000到目前为止已经花了20分钟，而且还在继续。很明显，我在这里的做法是错误的（是的，这个程序确实有效，我用较小的数字进行了尝试）。有人能提出一种不那么详尽的方法吗？

Answer 1

公共类LargestPrimeFactor{

public static boolean isPrime(long num){
    int count = 0;
    for(long i = 1; i<=num/2 ; i++){
        if(num % i==0){
            count++;
        }
    }
    if(count==1){
        return true;
    }
    return false;
}

public static String largestPrimeFactor(long num){
    String factor = "none";
    for(long i = 2; i<= num/2 ; i++){
        if(num % i==0 && isPrime(i)){
           factor = Long.toString(i); 
        }
    }
    return factor;     
}
public static void main(String[] args) {
    System.out.println(largestPrimeFactor(13195));
}

}

Answer 2

public static void main(String[] args) {

    long number = 600851475143L;

    long highestPrime = -1;
    for (long i = 2; i <= number; ++i) {
        if (number % i == 0) {
            highestPrime = i;
            number /= i;
            --i;
        }
    }

    System.out.println(highestPrime);
}

Answer 3

试试这个。。

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));
}
}