Простые числа в Java - Алгоритмы

Question

Простые числа в Java - Алгоритмы

Я начал изучать код на Java и решил, что буду использовать сайт Project Euler, чтобы дать мне небольшие задачи, которые я хочу попробовать выполнить с каждым новым фрагментом кода, который я изучаю. Итак, я столкнулся с проблемой 3:

Основными коэффициентами 13195 являются 5, 7, 13 и 29. Какой самый большой главный фактор числа 600851475143?

Я подумал о проблеме и исследовал множество различных теорий о простых числах и о том, как их можно найти с помощью различных различных вычислений (в качестве примера используется Sieve of Eratosthenes), и решение, которое я придумал, состояло в том, чтобы проверить числа от 2 -> n и посмотреть, они были бы простым числом, если бы они были тогда, я бы разделил переменную Tn (в данном случае 600851475143) на вновь открытое простое число и посмотрел бы, был ли это фактор. Если бы это было так, я бы назначил его переменной Hp (наивысшее простое число) и в конце программы вывел бы Hp на консоль, чтобы получить мой результат.

Вот мой код:

public class Largest_Prime_Factor_NEW_SOLUTION {

    static long Tn = 600851475143L;
    static long Hp = 0;
    static boolean isPrime = false;

    public static void main(String[] args) {

        for (long i=2; i<Tn; i++) {
            System.out.println("TESTING NUMBER " + i);
            for (long k=2; k < i; k++) {
                if (i % k == 0) {
                    System.out.println(i + " IS NOT A PRIME");
                    break;
                } else if (k + 1 == i) {
                    isPrime = true;
                }
            }

            if (isPrime) {
            System.out.println(i + " IS A PRIME");
            if (Tn % i == 0) {
                System.out.println(Tn + " IS DIVISIBLE BY " + i);
                Hp = i;
            } else {
                System.out.println(Tn + " IS NOT DIVISIBLE BY " + i);
            }
            }

            isPrime = false;
        }
        System.out.println("THE HIGHEST PRIME NUMBER OF " + Tn + " IS " + Hp);
    }
}

Теперь я знаю, что этот код очень неэффективен, и для начала мне удалось сжать его с того места, с которого я начал (везде были циклы!), Но я спрашиваю, как я могу улучшить это? Это поглощает меня, потому что все, что я исследую, противоречит тому, что делают другие, и это очень запутанно. Я пробовал метод sieve, но я понимаю, что логический массив может быть только массивом int, а не длинным массивом?

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

2

java algorithm math primes

Источник

user1145909 21 июл '13 в 10:30

6 ответов

Решение

Спасибо за вашу помощь, после прочтения комментариев и ответов мне удалось сжать код гораздо дальше:

    public class Largest_Prime_Factor_NEW_SOLUTION_2 {

    static long Tn = 600851475143L;

    public static void main(String[] args) {

        for (long i = 2; i < Math.sqrt(Tn); i++) {

            if(Tn % i == 0) {
                Tn = Tn / i;
                i--;
            }   
        }
        System.out.println(Tn);
    }
}

и работает отлично! Еще раз спасибо за вашу помощь и время, чтобы помочь мне понять. Я понимаю, что это была скорее математическая проблема, чем проблема кодирования, но она помогла мне понять несколько вещей. Я теперь, чтобы узнать что-то еще:)

1

Источник

user1145909 21 июл '13 в 12:33

Простой алгоритм для вычисления составного числа методом пробного деления выглядит следующим образом:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            fs.append(f)
            n := n / f
        f := f + 1
    if n > 1
        fs.append(n)
    return fs

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

0

Источник

user448810 21 июл '13 в 12:25

Поскольку вы делаете это как учебное упражнение, когда вы достаточно улучшили свою текущую программу, почему бы не попробовать решить ту же проблему другим способом? Метод факторизации Ферма сначала находит большие факторы.

0

Источник

user820127 21 июл '13 в 11:06

Это Java-версия этого:

 static boolean isPrime(int n){
    if (n == 2) return true;
    if (n == 3) return true;
    if (n % 2 == 0) return false;
    if (n % 3 == 0) return false;

    int i = 5;
    int w = 2;
    while (i * i <= n) {
        if(n % i == 0)
        return false;

        i += w;
        w = 6 - w;
    }
    return true;
}

Как описано @Alexandru: Это вариант классического алгоритма O(sqrt(N)). Он использует тот факт, что простое число (кроме 2 и 3) имеет форму 6k-1 и 6k+1 и смотрит только на делители этой формы.

0

Источник

user732328 29 июн '15 в 09:02

Есть много способов улучшить программу, подобную этой, но улучшения касаются в основном математики, а не программирования:

При поиске факторов проверяйте каждое число, а не только простые числа. Если вы найдете фактор, проверьте, является ли он основным. Таким образом вы избавите себя от многих проверок первичности.
Наибольший простой множитель составного числа может быть не более квадратного корня числа, поэтому вы можете остановить итерацию раньше.
Используйте быстрый тест на простоту вместо пробных делений http://en.wikipedia.org/wiki/Primality_test

Опять же, это разовое. Не переусердствуйте.

0

Источник

user318758 21 июл '13 в 10:56

Другие вопросы по тегам java algorithm math primes

user1682673 21 июл '13 в 10:40 2013-07-21 10:40 · Accepted Answer · 2013-07-21 10:40

Что вы можете сделать, это найти самый низкий делитель Tn, Предположим, что это pнайти нижний делитель снова для Tn/p и так далее.

Теперь на каждом шагу p прост [объяснение ниже]. Так что собирайте их, и они являются главными делителями Tn,

Для лучшей сложности времени вы можете проверить делители до ceil(sqrt(Tn)) только вместо Tn-1,

И когда вы начинаете проверять на делитель для Tn, вы можете начать с 2, И как только вы получите простой делитель p не начинай снова с 2 за Tn/p, Так как, Tn/p также является делителем Tn и с тех пор Tn не имеет делителей меньше чем p, Tn/p его тоже нет. Итак, начнем с p снова[p может иметь несколько сил в Tn]. Если p не делит Tn, перейти к p+1,

Пример:

Tn = 45
1. начать с 2. 2 не делит 45.
2. следующий тест для 3. 45 делится на 3. Таким образом, 3 является его основным делителем.
3. Теперь проверьте простые делители от 45/3 = 15, но начните с 3., а не с 2 снова. 4. Хорошо, 15 делится на 3. Итак, начнем с 15/3 = 5 5. Обратите внимание, что для 5 ceil(sqrt(5)) равен 3. Но 5 не делится на 3. Но так как 4 > ceil(sqrt(5)) и мы можем сказать, что 5 простое число без каких-либо сомнений.

Таким образом, главный делитель 45 - это 3 и 5.

Почему наименьший делитель (кроме 1) числа является простым?

Предположим, что приведенное выше утверждение неверно. Тогда число N имеет наименьший, но составной делитель, скажем C.

Итак, C|N Теперь C составно, поэтому у него делитель меньше, чем он сам, но больше единицы.
Скажем, таким делителем C является P.
Итак, P|C, но мы имеем C|N => P|N, где 1

Это противоречит нашему предположению, что C является наименьшим делителем числа N, поэтому наименьшие делители числа всегда являются простыми числами.