Java中的Prime分解程序 [英] Prime Factorization Program in Java

问题描述

我正在研究用Java实现的素数分解程序。
目标是找到最大的素数因子600851475143（项目欧拉问题3 ）。
我想我已经完成了大部分工作，但我收到了一些错误。
此外我的逻辑似乎已关闭，特别是我设置的用于检查数字是否为素数的方法。

I am working on a prime factorization program implemented in Java. The goal is to find the largest prime factor of 600851475143 (Project Euler problem 3). I think I have most of it done, but I am getting a few errors. Also my logic seems to be off, in particular the method that I have set up for checking to see if a number is prime.

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;
    }
}

推荐答案

为什么让它变得如此复杂？您不需要执行 isPrime（）之类的操作。除以它的最小除数（素数）并从这个素数做循环。这是我的简单代码：

Why make it so complicated? You don't need do anything like isPrime(). Divide it's least divisor(prime) and do the loop from this prime. Here is my simple code :

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));
    }
}

这篇关于Java中的Prime分解程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！