Программа Prime Factorization на Java

Question

Я работаю над основной программой факторизации, реализованной на Java. Цель состоит в том, чтобы найти наибольший простой фактор 600851475143 ( Project Euler problem 3 ). Я думаю, что я сделал большую часть этого, но я получаю несколько ошибок. Также, кажется, моя логика отключена, в частности, метод, который я настроил для проверки, является ли число простым.

public class PrimeFactor {

    public static void main(String[] args) {
        int count = 0;
        for (int i = 0; i < Math.sqrt(600851475143L); i++) {
            if (Prime(i) && i % Math.sqrt(600851475143L) == 0) {
                count = i;
                System.out.println(count);
            }
        }
    }

    public static boolean Prime(int n) {
        boolean isPrime = false;
        // A number is prime iff it is divisible by 1 and itself only
        if (n % n == 0 && n % 1 == 0) {
            isPrime = true;
        }
        return isPrime;
    }
}

Редактировать

public class PrimeFactor {

    public static void main(String[] args) {
        for (int i = 2; i <= 600851475143L; i++) {
            if (isPrime(i) == true) {
                System.out.println(i);
            }
        }
    }

    public static boolean isPrime(int number) {
        if (number == 1) return false;
        if (number == 2) return true;
        if (number % 2 == 0) return false;
        for (int i = 3; i <= number; i++) {
            if (number % i == 0) return false;
        }
        return true;
    }
}

Answer 1

Зачем делать это так сложно?Вам не нужно делать что-то вроде isPrime () .Разделите его наименьший делитель (простое число) и сделайте цикл из этого простого числа.Вот мой простой код:

public class PrimeFactor {

    public static int largestPrimeFactor(long number) {
        int i;

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

        return i;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(largestPrimeFactor(13195));
        System.out.println(largestPrimeFactor(600851475143L));
    }
}

Answer 2

редактировать: я надеюсь, что это не звучит как снисходительный ответ. Я просто очень хотел проиллюстрировать, что с точки зрения компьютера, вы должны проверить все возможные числа, которые могут быть факторами X, чтобы убедиться, что оно простое. Компьютеры не знают , что они составные, просто взглянув на них, поэтому вам нужно повторить

Пример: X - простое число?

Для случая, когда X = 67:

Как это проверить?

I divide it by 2... it has a remainder of 1 (this also tells us that 67 is an odd number)
I divide it by 3... it has a remainder of 1
I divide it by 4... it has a remainder of 3
I divide it by 5... it has a remainder of 2
I divide it by 6... it has a remainder of 1

Фактически, вы получите остаток от 0, только если число не простое.

Вам нужно проверять каждое число меньше X, чтобы убедиться, что оно простое? Нету. Больше нет, благодаря математике (!)

Давайте посмотрим на меньшее число, например 16.

16 не простое число.

почему? потому что

2*8 = 16
4*4 = 16

Таким образом, 16 делится поровну более чем на 1 и на себя. (Хотя «1» технически не простое число, но это технические детали, и я отвлекся)

Итак, мы делим 16 на 1 ... конечно, это работает, это работает для каждого числа

Divide 16 by 2... we get a remainder of 0  (8*2)
Divide 16 by 3... we get a remainder of 1  
Divide 16 by 4... we get a remainder of 0  (4*4)
Divide 16 by 5... we get a remainder of 1
Divide 16 by 6... we get a remainder of 4
Divide 16 by 7... we get a remainder of 2
Divide 16 by 8... we get a remainder of 0  (8*2)

Нам действительно нужен только один остаток от 0, чтобы сказать нам, что он составной (противоположность «простому» - «составной»).

Проверка, делится ли 16 на 2, это то же самое, что проверка деления на 8, потому что 2 и 8 умножаются, чтобы дать вам 16.

Нам нужно только проверить часть спектра (от 2 до квадратного корня из X), потому что наибольшее число, которое мы можем умножить, равно sqrt (X), в противном случае мы используем меньшие числа для получения избыточных ответов. .

17 простых?

17 % 2 = 1
17 % 3 = 2
17 % 4 = 1 <--| approximately the square root of 17 [4.123...]
17 % 5 = 2 <--|
17 % 6 = 5
17 % 7 = 3

Результаты после sqrt (X), такие как 17 % 7 и т. Д., Являются избыточными, поскольку они обязательно должны умножаться на что-то меньшее, чем sqrt (X), чтобы получить X.

То есть

A * B = X

если A и B оба больше sqrt (X), то

A * B даст число, большее X.

Таким образом, одно из значений A или B должно быть меньше, чем sqrt (X), и излишне проверять оба этих значения, поскольку вам нужно только знать, делит ли одно из них X равномерно (четное деление дает вам другое значение в качестве ответа)

Надеюсь, это поможет.

edit: в BigInteger , как я недавно узнал, есть более сложные методы проверки простоты, и в Java есть встроенный метод «это число, вероятно, простое число» или «это число определенно составное». через другой SO ответ:]

Answer 3

Вот очень элегантный ответ - который использует грубую силу (не какой-то причудливый алгоритм), а умным способом - путем уменьшения предела, когда мы находим простые числа и делим их на эти простые числа ...печатает только простые числа - и только простые числа, и если одно простое число больше, чем один раз в продукте - оно напечатает его столько раз, сколько это простое число находится в продукте.

    public class Factorization {
    public static void main(String[] args) {
    long composite = 600851475143L;
    int limit = (int)Math.sqrt(composite)+1;
    for (int i=3; i<limit; i+=2)
    {
        if (composite%i==0)
        {
            System.out.println(i);
            composite = composite/i;
            limit = (int)Math.sqrt(composite)+1;
            i-=2;   //this is so it could check same prime again
        }
    }
    System.out.println(composite);
    }
}

Answer 4

Вам нужно провести некоторое исследование алгоритмов факторизации больших чисел; эта страница википедии выглядит как хорошее место для начала.В первом абзаце говорится:

Когда числа очень велики, общеизвестный эффективный алгоритм факторизации целого числа не известен ...

, но в нем перечислено числоалгоритмов специального и общего назначения.Вам нужно выбрать тот, который будет работать достаточно хорошо, чтобы иметь дело с 12 десятичными цифрами.Эти числа слишком велики для самого наивного подхода к работе, но достаточно малы, чтобы (например) подход, основанный на перечислении простых чисел, начиная с 2, работал.(Подсказка - начните с Решета Эрастонов)

Answer 5

Чтобы найти факторы, вы хотите что-то вроде:

long limit = sqrt(number);
for (long i=3; i<limit; i+=2)
    if (number % i == 0)
        print "factor = " , i;

В этом случае все факторы достаточно малы (<7000), поэтому их поиск должен занять меньше секунды, даже с таким наивным кодом, как этот. Также отметьте, что у этого конкретного числа есть другие, меньшие, главные факторы. Для такого поиска методом грубой силы вы можете сэкономить небольшую работу, разделив меньшие факторы по мере их нахождения, а затем выполнить простую факторизацию полученного меньшего числа. Преимущество состоит в том, чтобы указывать только основные факторы. В противном случае вы также получите составные факторы (например, у этого числа есть четыре основных фактора, поэтому первый метод выведет не только основные факторы, но и произведения различных комбинаций этих основных факторов). </p>

Если вы хотите немного оптимизировать это, вы можете использовать сито Эратосфена, чтобы найти простые числа вплоть до квадратного корня, а затем только пытаться делить на простые числа. В этом случае квадратный корень равен ~ 775'000, и вам нужен только один бит на число, чтобы указать, простое ли оно. Вы также (обычно) хотите хранить только нечетные числа (поскольку вы сразу знаете, что все четные числа, кроме двух, составные), поэтому вам нужно ~ 775'000 / 2 бита = ~ 47 килобайт.

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

Answer 6

Вы хотите выполнить итерацию из 2 -> n-1 и убедиться, что n% i! = 0. Это самый наивный способ проверки на простоту.Как объяснено выше, это очень очень медленно, если число большое.

Answer 7

    private static boolean isPrime(int k) throws IllegalArgumentException
     {
        int j;

        if (k < 2) throw new IllegalArgumentException("All prime numbers are greater than 1.");
        else {
            for (j = 2; j < k; j++) {
                if (k % j == 0) return false;
            }
        }

        return true;
    }

    public static void primeFactorsOf(int n) {
        boolean found = false;

        if (isPrime(n) == true) System.out.print(n + " ");
        else {
            int i = 2;
            while (found == false) {
                if ((n % i == 0) && (isPrime(i))) {
                    System.out.print(i + ", ");
                    found = true;
                } else i++;
            }
            primeFactorsOf(n / i);
        }
    }

Answer 8

Я думаю, вы запутались, потому что нет оператора iff [if-and-only-if].

Хороший способ перехода к квадратному корню из целого числа, о котором идет речь. Осталось только проверить, делится ли число в этом цикле равномерно. Это просто [большое число]% i == 0. Для вашей функции Prime нет причин.

Так как вы ищете самый большой делитель, другой трюк будет начинаться с наивысшего целого числа, меньшего квадратного корня, и идти i -.

Как и другие говорили, в конце концов, это очень медленно.

Answer 9

public class Prime
{
 int i;   

 public Prime( )
 {
    i = 2;
 }

 public boolean isPrime( int test ) 
 {
    int k;

    if( test < 2 )
        return false;
    else if( test == 2 )  
        return true;
    else if( ( test > 2 ) && ( test % 2 == 0 ) )
        return false;
    else
    {
        for( k = 3; k < ( test/2 ); k += 2 )
        {
            if( test % k == 0 ) 
                return false;
        }

    }

    return true;

 }

 public void primeFactors( int factorize )
 {
    if( isPrime( factorize ) )
    {
        System.out.println( factorize );
        i = 2;
    }
    else
    {
        if( isPrime( i ) && ( factorize % i == 0 ) )
        {
            System.out.print( i+", " );
            primeFactors( factorize / i );
        }
        else
        {
            i++;
            primeFactors( factorize );
        }
   }

   public static void main( String[ ] args )
   {
       Prime p = new Prime( );

       p.primeFactors( 649 );
       p.primeFactors( 144 );
       p.primeFactors( 1001 );
   }
}

Answer 10

У меня очень похожая проблема для моего класса программирования. В моем классе он должен был рассчитать для введенного числа. Я использовал решение, очень похожее на Stijak. Я отредактировал свой код, чтобы сделать число из этой проблемы вместо использования ввода.

Некоторые отличия от кода Стиджака заключаются в следующем:

Я учел четные числа в моем коде.

Мой код печатает только самый главный фактор, а не все факторы.

Я не пересчитываю factorLimit, пока не разделю все экземпляры текущего фактора.

Все переменные были объявлены как длинные, потому что я хотел использовать их для очень больших значений числа. Я обнаружил, что в худшем случае было очень большое простое число, например, 9223372036854775783, или очень большое число с квадратным корнем из простого числа, например, 9223371994482243049. Чем больше факторов число, тем быстрее работает алгоритм. Следовательно, лучшим вариантом будет число, например 4611686018427387904 (2 ^ 62) или 6917529027641081856 (3 * 2 ^ 61), поскольку оба имеют 62 фактора.

public class LargestPrimeFactor
{
    public static void main (String[] args){
        long number=600851475143L, factoredNumber=number, factor, factorLimit, maxPrimeFactor;
        while(factoredNumber%2==0)
            factoredNumber/=2;
        factorLimit=(long)Math.sqrt(factoredNumber);
        for(factor=3;factor<=factorLimit;factor+=2){
            if(factoredNumber%factor==0){
                do  factoredNumber/=factor;
                while(factoredNumber%factor==0);
                factorLimit=(long)Math.sqrt(factoredNumber);
            }
        }
        if(factoredNumber==1)
            if(factor==3)
                maxPrimeFactor=2;
            else
                maxPrimeFactor=factor-2;
        else
            maxPrimeFactor=factoredNumber;
        if(maxPrimeFactor==number)
            System.out.println("Number is prime.");
        else
            System.out.println("The largest prime factor is "+maxPrimeFactor);
    }
}