最大质因数程序执行时间非常长 - Java

Question

这是欧拉计划中的第3个问题。对于那些不知道的人，我需要找出600851475143的最大质数因子。以下是我的代码：

import java.lang.Math;
// 600851475143
public class LargestPrimeFactor {
    public static void main(String[] stuff) {
        long num = getLong("What number do you want to analyse? ");
        long[] primes = primeGenerator(num);
        long result = 0;
        for(int i = 0; i < primes.length; i++) {
            boolean modulo2 = num % primes[i] == 0;
            if(modulo2) {
                result = primes[i];
            }
        }
        System.out.println(result);
    }
    public static long[] primeGenerator(long limit) {
        int aindex = 0;
        long[] ps = new long[primeCount(limit)];
        for(long i = 2; i < limit + 1; i++) {
            if(primeCheck(i)) {
                ps[aindex] = i;
                aindex++;
            }
        }
        return ps;
    }

    public static boolean primeCheck(long num) {
        boolean r = false;
        if(num == 2 || num == 3) {
            return true;
        }
        else if(num == 1) {
            return false;
        }
        for(long i = 2; i < Math.sqrt(num); i++) {
            boolean modulo = num % i == 0;
            if(modulo) {
                r = false;
                break;
            }
            else if(Math.sqrt(num) < i + 1 && !modulo) {
                r = true;
                break;
            }
        }
        return r;
    }
    public static int primeCount(long limit) {
        int count = 0;
        if(limit == 1 || limit == 2) {
            return 0;
        }
        for(long i = 2; i <= limit; i++) {
            if(primeCheck(i)) {
                count++;
            }
        }
        return count;
    }
public static long getLong(String prompt) {
    System.out.print(prompt + " ");
    long mrlong = input.nextLong();
    input.nextLine();
    return mrlong;
}
}

但是当我使用比600851475143小得多的数字进行测试，例如100000000时，程序需要花费很长时间 - 实际上，100000000已经花费了20分钟，但还在继续。显然，我在这里采用了错误的方法（是的，该程序确实有效，我已经尝试过较小的数字）。有人能建议一种更少费力的方法吗？

- Bluefire

---

你读过一些关于质数的数学书吗？它们提供了更聪明的算法！ - Basile Starynkevitch

为什么不尝试使用“埃拉托斯特尼筛法”来实现您的质数检查呢？Sieve of Eratosthenes - Kazekage Gaara

你为什么要生成小于等于num的质数而不是num的平方根？如果一个数不是质数，那么它必然有一个因子小于或等于它的平方根。此外，像Kazekage所说的那样，你应该研究一下筛法。 - David Conrad

@DavidConrad - 我是。for(long i = 2; i < Math.sqrt(num); i++) - Bluefire

@Bluefire 在primeGenerator和primeCount函数中，你的循环范围是limit，这会生成6000亿以内的质数，但实际上你只需要生成小于等于limit平方根的质数，大约是77.5万。（你还应该将循环条件改为小于等于limit的平方根，并且可以简化primeCheck函数）。通过这个改变，你的程序在我的笔记本电脑上运行时间缩短到了1.2秒。 - David Conrad

另一个关于同样问题的最近讨论：https://dev59.com/X2fWa4cB1Zd3GeqPg3Dw - Will Ness

Answer 1

公共类 LargestPrimeFactor {

public static boolean isPrime(long num){
    int count = 0;
    for(long i = 1; i<=num/2 ; i++){
        if(num % i==0){
            count++;
        }
    }
    if(count==1){
        return true;
    }
    return false;
}

public static String largestPrimeFactor(long num){
    String factor = "none";
    for(long i = 2; i<= num/2 ; i++){
        if(num % i==0 && isPrime(i)){
           factor = Long.toString(i); 
        }
    }
    return factor;     
}
public static void main(String[] args) {
    System.out.println(largestPrimeFactor(13195));
}

}

- Deeps

Answer 2

public static void main(String[] args) {

    long number = 600851475143L;

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

    System.out.println(highestPrime);
}

- bm1729

Answer 3

我已经完成了Project Euler上的几十个挑战。其中一些问题可以用蛮力法解决（尽管他们建议不要这样做），但其他一些问题则需要“出奇制胜”的思维方式。你无法靠蛮力解决那个问题。

网络上有很多帮助可以引导你朝着正确的方向前进，例如： http://thetaoishere.blogspot.com.au/2008/05/largest-prime-factor-of-number.html

- Elliot Chance

---

警告：我不小心发布了解决方案（用另一种语言） - Elliot Chance

Answer 4

一个数的质因子个数总是小于该数的平方根，因此无需迭代该数n以找到其最大质因子。

看看这段代码。

    public class LargestPrimeFactor {
        public static void main(String[] args) {

            Scanner sc=new Scanner(System.in);
            long num=sc.nextLong();

            if(num>0 && num<=2)
            {
                System.out.println("largest prime is:-" + num);
                System.exit(0);
            }

            int i=((Double)Math.sqrt(num)).intValue();
            int j=3;
            int x=0;

            //used for looping through the j value which can also be a prime. for e.g in case of 100 we might get 9 as a divisor. we need to make sure divisor is also a prime number.
            int z=0;
//same function as j but for divisor
            int y=3;
            int max=2;
//divisor is divisible
            boolean flag=false;
//we found prime factors
            boolean found=false;

            while(x<=i)
            {
                y=3;
                flag=false;

                if(num % j ==0)
                {
                    if(j>max)
                    {
                        for(z=0;z<Math.sqrt(j);z++)
                        {
                            if(j!=y && j % y==0)
                            {
                                flag=true;
                            }
                            y+=2;
                        }
                        if(!flag)
                        {
                            found=true;
                            max=j;
                        }
                    }
                }
                j+=2;
                x++;
            }
            if(found){
                System.out.println("The maximum prime is :- " + max);
            }
            else
            {
                System.out.println("The maximum prime is :- " + num);   
            }
        }
    }

- ATR

Answer 5

更改

for(long i = 2; i <= limit; i++)

为

// add the one for rounding errors in the sqrt function
new_limit = sqrt(limit) + 1;
// all even numbers are not prime 
for(long i = 3; i <= new_limit; i+=2)
{
...
}

例如，对于因数分解1000000，它只需要进行大约500次迭代，而不是迭代1000000次。

- user3715912