Программа 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

Чтобы найти все простые факторизации

import java.math.BigInteger;
import java.util.Scanner;


public class BigIntegerTest {


     public static void main(String[] args) {


            BigInteger myBigInteger = new BigInteger("65328734260653234260");//653234254
            BigInteger originalBigInteger;
            BigInteger oneAddedOriginalBigInteger;
            originalBigInteger=myBigInteger;
            oneAddedOriginalBigInteger=originalBigInteger.add(BigInteger.ONE);
            BigInteger index;
            BigInteger countBig;


            for (index=new BigInteger("2");  index.compareTo(myBigInteger.add(BigInteger.ONE)) <0; index = index.add(BigInteger.ONE)){

                countBig=BigInteger.ZERO;
                while(myBigInteger.remainder(index) == BigInteger.ZERO ){
                    myBigInteger=myBigInteger.divide(index);
                    countBig=countBig.add(BigInteger.ONE);
                }

                if(countBig.equals(BigInteger.ZERO)) continue;
                System.out.println(index+ "**" + countBig);

            }
            System.out.println("Program is ended!");
     }
}

Answer 2

Для тех ответов, которые используют метод isPrime(int) : boolean, существует более быстрый алгоритм, чем ранее реализованный (что-то вроде)

private static boolean isPrime(long n) { //when n >= 2
    for (int k = 2; k < n; k++)
        if (n % k == 0) return false;

    return true;
}

и это так:

private static boolean isPrime(long n) { //when n >= 2
    if (n == 2 || n == 3) return true;

    if (n % 2  == 0 || n % 3 == 0) return false;

    for (int k = 1; k <= (Math.floor(Math.sqrt(n)) + 1) / 6; k++)
        if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0) return false;

    return true;
}

Я сделал этот алгоритм, используя два факта:

1. Нам нужно проверить только n % k == 0 до k <= Math.sqrt(n). Это правда, потому что для чего-то более высокого, факторы просто «переворачивают» бывших. рассмотрим случай n = 15, где 3 * 5 = 5 * 3 и 5> Math.sqrt(15). Нет необходимости в таком совпадении проверки как 15 % 3 == 0, так и 15 % 5 == 0, когда мы можем просто проверить одно из этих выражений.
2. Все простые числа (кроме 2 и 3) могут быть выражены в виде (6 * k) + 1 или (6 * k) - 1, потому что любое положительное целое число может быть выражено в виде (6 * k) + n, где n = -1, 0, 1, 2, 3, or 4 и k является целым числом <= 0, и случаи, когда n = 0, 2, 3, and 4 все приводимы.

Следовательно, n является простым, если оно не делится на 2, 3 или на некоторое целое число вида 6k ± 1 <= Math.sqrt(n). Отсюда и вышеприведенный алгоритм.

-

Статья в Википедии о тестировании на простоту

-

Редактировать: Думаю, что я мог бы также опубликовать свое полное решение (* я не использовал isPrime(), и мое решение почти идентично верхнему ответу, но я подумал, что должен ответить на фактический вопрос):

public class Euler3 {

    public static void main(String[] args) {
        long[] nums = {13195, 600851475143L};

        for (num : nums)
            System.out.println("Largest prime factor of " + num + ": " + lpf(num));

    }

    private static lpf(long n) {
        long largestPrimeFactor = 1;
        long maxPossibleFactor = n / 2;

        for (long i = 2; i <= maxPossibleFactor; i++)
            if (n % i == 0) {
                n /= i;
                largestPrimeFactor = i;

                i--;
            }

            return largestPrimeFactor;

    }

}