Создание решения для Project Euler более эффективным

Question

Изначально у меня были некоторые проблемы с работой этого кода, но после небольшой настройки я его отладил и готов к работе.

Я прошел несколько ревизий этой программы.Я начал с целочисленных значений только для того, чтобы найти, что число было слишком большим, чтобы поместиться в int.Затем я перешел на BigIntegers, который оказался хлопотным, но работоспособным.Оттуда я переключился на long (как следовало бы сделать с самого начала) и сократил время выполнения моего кода в 8 раз (или более).

Вот код, который есть сейчас:

long qNum = 600851475143L;

for (long i = qNum - 1L; i * i >= qNum; i -= 2L)
    if (qNum % i == 0 && isPrime(i)) {
        System.out.println("Solution:" + i); // for debugging
        return i;
    }
    else
        System.out.println(i);// for debugging

return 0L;

И

public static boolean isPrime(long num) {
    // unnecessary if statement for this problem (b/c of for loop), but useful for others 
    if (num % 2 == 0)
        return false;

    for (long i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;

    return true;
}

Он работает несколько часов и ничего не нашел.В интернете я увидел, что решение этой головоломки типично, как разбор 560 ГБ данных = /.

Какие-нибудь советы по ускорению этого процесса?

Большое спасибо,

Justian

РЕДАКТИРОВАТЬ:

Оптимизированный код:

public static long greatestPrimeFactor(ArrayList<Long> factors, long num) {
    for (long i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            factors.add(i);
            return greatestPrimeFactor(factors, num / i);
        }
    }

    for (int i = factors.size()-1; i > 0; i--)
        if (isPrime(factors.get(i)))
            return num;

    return 0;
}

И

public static boolean isPrime(long num) {
if (num % 2 == 0)
    return false;

for (long i = 3; i * i <= num; i += 2)
    if (num % i == 0)
        return false;

    return true;
}

Выполнить с

greatestPrimeFactor(new ArrayList<Long>(), 600851475143L);

Answer 1

Вы делаете слишком много ненужных вещей.Вот более простое решение:

long greatestFactor(long n) {
    long p = 0;
    for (long k = 2; k * k <= n; k++)
        while (n % k == 0) {
            n /= k;
            p = k;
        }
    if (n > 1)
        p = n;
    return p;
}

Answer 2

Мое решение попадает менее чем за сотую долю секунды. Каждый раз, когда вы найдете делитель числа, разделите число на этот делитель и начните снова. Наибольшее число, на которое вы делите, является вашей целью.

Answer 3

В python вы можете просто вычислить все простые множители, а затем использовать функцию max, например:

def calc_prime_factors(n,i=2,result=[]):
  while i<=n:
    while n%i!=0:
      i+=1
    result.append(i)
    if n!=1:
      n,i=n/i,2
    else:
      break
  return result

print max(calc_prime_factors(600851475143))

Answer 4

Вам не нужно проверять каждое число на предмет того, является ли оно простым. Вы видите это, поэтому вы проверяете только каждый номер ODD (ну и 2). Вы можете пойти дальше! Создайте таблицу из первых нескольких миллионов простых чисел и сравните только с ними. Вы будете двигаться намного быстрее, с очень маленькими накладными расходами.

Редактировать: Вот о чем я говорил. Это довольно просто. Обратите внимание, как я сравниваю только значения с уже вычисленными простыми числами. Как только вы вычислили достаточное их количество (скажем, первые 10000000 простых чисел), начните выполнять поиск на основе метода +2, как и вы. Имейте в виду, что большинство из них будут пойманы рано, потому что вы пропускаете ненужные номера. Вам не нужно тестировать 15,25,35,45,55 и т. Д., Потому что вы уже протестировали 5. Это само по себе отбраковывает около 20% ваших тестов, что легко объясняет накладные расходы на вычисление Первые несколько миллионов номеров.

Пример вывода

C:\files\j\misc>java sandbox2
resized to 200
resized to 400
resized to 800
resized to 1600
resized to 3200
resized to 6400
resized to 12800
resized to 25600
resized to 51200
resized to 102400
resized to 204800
resized to 409600
resized to 819200
664579 primes in 18 seconds. Last prime was 9999991

C:\files\j\misc>

Пример кода:

public class sandbox2 {
    static int[] primes = new int[100]; // where the primes really are
    static int count = 0;
    static long mostRecentPrime;

    public static void main(String[] args) throws Exception {
        addPrime(2); // give it a couple to start
        addPrime(3);
        addPrime(5);
        long start = System.currentTimeMillis();
        for(long i = 7; i < 10000000; i++) { // all primes less than 10M
            if(isPrime(i)) addPrime(i);            
        }        
        long end = System.currentTimeMillis();
        long time = (end-start) / 1000;
        System.out.println(count + " primes in " + time + " seconds. Last prime was " + mostRecentPrime);
    }    
    public static boolean isPrime(long i) {
        long max = (long)(Math.sqrt(i))+1;
        for(int pos = 0; primes[pos] < max && pos < primes.length; pos++) {
            long prime = (long)(primes[pos]);
            if(i % prime == 0) return false;
        }
        return true;
    }    
    public static void addPrime(long p) {
        mostRecentPrime = p;
        if(count == primes.length) { // resize if necessary
            int size = primes.length * 2;
            int[] newprimes = new int[size];
            System.arraycopy(primes, 0, newprimes, 0, primes.length);
            primes = newprimes;
            System.out.println("resized to " + primes.length);
        }
        primes[(int)count] = (int)p;
        count++;
    }
}