Ява самый большой главный фактор длинного

Question

Я пытаюсь найти самый большой главный фактор из большого числа. Например, если бы это число было 573849284703, мой код выглядел бы так:

public static void main(String[] args) {

    long number = 573849284703l;

    System.out.println(lgstprmfactor(number));

}

public static long lgstprmfactor(long number) {
    for (long i = 286924642352l; i > 0; i--) {
        if (number % i == 0 && isPrime(i) == true) {
            long answer = i;
            return answer;
        }
    }
    return 0;
}

public static boolean isPrime(long i) {
    for (long c = 2; c < i; c++) {
        if (i % c == 0)
            return false;
    }
    return true;
}

Но чтобы работать, нужны какие-то предложения, чтобы ускорить или оптимизировать код в целом?

Answer 1

public static void main(String[] args)
 {
  long startTime = System.currentTimeMillis();
  System.out.println(largestprimefactor(573849284703l));
  long endTime = System.currentTimeMillis();
  System.out.println(endTime - startTime+" ms ");
 }

public static int largestprimefactor(long l)
{
    int i;
    long copyofinput = l;
    for(i=2;i<copyofinput;i++)
    {
        if(copyofinput%i==0){

            copyofinput/=i;
            i--;
        }
    }

    return i;
}

}

выход: 66718903

688 мс

Answer 2

Одним из быстрых решений для улучшения времени выполнения может быть реализация вашего алгоритма в нескольких потоках, которые одновременно проверяют, является ли число основным фактором для разных диапазонов. Т.е. создать поток, который проверяет, является ли он простым множителем между 0 и 1000000, затем поток для 1000001+ и т. Д.

Answer 3

Основные идеи здесь: удаляйте простые множители по мере их нахождения, не ищите больше, чем квадратный корень из оставшегося числа, и пропускайте четные числа (кроме 2). Я также добавил некоторые проверки ошибок и другие украшения.

public static void main(String[] args)
{
    try {
        System.out.println(largestPrimeFactor(573849284703l));
    } catch (ArithmeticException e) {
        System.out.println("Error factoring number: " + e.getMessage());
    }
}

private static long sqrtint(long n) {
  return (long)Math.sqrt(n + 0.5);
}

public static int largestPrimeFactor(long n) throws ArithmeticException
{
    if (n < 2) throw new ArithmeticException(n + " < 2");
    while (n%2 == 0) n /= 2;
    if (n < 2) return 2;
    long i, root = sqrtint(n);
    for(i=3; i<root; i+=2)
    {
        if(n%i == 0) {
            n /= i;
            while (n%i==0) n /= i;
            if (n == 1) return i;
            root = sqrtint(n);
        }
    }

    return n;
}

}