Проект Euler # 3 на Java; программа не выводит результат - PullRequest
Новая
       3

Проект Euler # 3 на Java; программа не выводит результат

1 голос
/ 27 марта 2020

Я пытаюсь решить проблему 3 в Project Euler:

Основные факторы 13195 - это 5, 7, 13 и 29.

Что является наибольшим основным фактором номер 600851475143?

Это мой код: 

import java.util.ArrayList;

public class Test {
    public static void main(String[] args){
        long max = 600851475143L;
        ArrayList<Long> primes = new ArrayList<>();
        primes.add((long) 2);
        boolean prime = true;
        for (long i = 3; i <= max; i += 2){
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime) primes.add(i);
            else prime = true;
        }
        for (int i = primes.size() - 1; i >= 0; i--){
            if (max % primes.get(i) == 0){
                System.out.println(primes.get(i));
                return;
            }
        }
    }
}

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

Ответы [ 2 ]

2 голосов
/ 27 марта 2020

Вы уверены, что ваша программа завершается? Я добавил следующий код ниже, и похоже, что первое для l oop займет много времени, поэтому, возможно, вы не видите никакого вывода. Чтобы увидеть ваши успехи, попробуйте добавить заявление для печати, как показано ниже: 

import java.util.ArrayList;

public class Test {

    public static void main(String[] args){
        long max = 600851475143L;
        ArrayList<Long> primes = new ArrayList<Long>();
        primes.add((long) 2);
        boolean prime = true;
        for (long i = 3; i <= max; i += 2){
            if(i % 1000005 == 0)
                System.out.println("i = " + i);
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime) primes.add(i);
            else prime = true;
        }
        for (int i = primes.size() - 1; i >= 0; i--){
            if (max % primes.get(i) == 0){
                System.out.println(primes.get(i));
                return;
            }
        }
    }
}
2 голосов
/ 27 марта 2020

Вы тратите время на вычисление всех простых чисел, когда у вас их тоже нет.

  • Когда вы найдете первое простое число, попробуйте уменьшить max на это простое число, пока оно не перестанет делиться.
  • Затем продолжайте находить следующее простое число.
  • и уменьшайте max, вычленяя это простое число.
  • каждый раз проверяйте, равно ли max текущему простому числу. Если это так, все готово.

Предполагая, что вы находите простые числа правильно (и я верю, что вы это делаете), подумайте о следующем: 

primes = 2,3,5,7,11,13
max = 99

is 99 divisible by 2 - no, try next prime.
is 99 divisible y  3 -  yes
max = 33
is 33 divisble by 3  - yes 
max = 11
is 11 divisible by 3 - no
by 5 - no
by 7 - no
by 11 - hey, max is a prime! And it must be the largest because
it can't be reduced anymore.

И, если хотите, при поиске каждого простой множитель max, сохраните его в списке.

Затем умножьте все значения в списке, чтобы увидеть, если продукт == max.

Вот ваш код 

import java.util.ArrayList;

public class Test {
    public static void main(String[] args){
        long max = 600851475143L;
          // right here, reduce max by current prime (which starts at 2)

        for (long i = 3; i <= max; i += 2){
            boolean prime = true;
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime)  {
            // right here, reduce max by current prime

            }
        }
    }
}
...