4

Project Euler 的问题 #3 是：

13195 的质因数是 5、7、13 和 29。

数字 600851475143 的最大质因数是多少？

我的解决方案需要永远。我认为我得到了正确的实施；但是，当使用大数字进行测试时，我无法看到结果。它永远运行。我想知道我的算法是否有问题：

public class LargestPrimeFactor3 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;
        long pFactor = 0;

        start = System.currentTimeMillis();

        for(int i = 2; i < num; i++) {
            if(isPrime(i)) {                
                if(num % i == 0) {
                    pFactor = i;                        
                }
            }
        }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println(pFactor + " Time: "+totalTime);
    }

    static boolean isPrime(long n) {

        for(int i = 2; i < n; i++) {
            if(n % i == 0) {
                return false;
            }
        }        
        return true;
    }     
}
4

9 回答 9

5

尽管不是在 Java 中，但我认为您可能可以理解以下内容。基本上，只需要测试奇数除数和一个数字的平方根来减少迭代。这是一种蛮力方法，可以在 C# 中立即产生结果。

static bool OddIsPrime (long oddvalue)  // test an odd >= 3 
{
    // Only test odd divisors.
    for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2)
    {
        if (value % i == 0)
            return false;
    }
    return true;
}

static void Main(string[] args)
{
    long max = 600851475143;   // an odd value
    long maxFactor = 0;

    // Only test odd divisors of MAX. Limit search to Square Root of MAX.
    for (long i = 3; i <= Math.Sqrt(max); i += 2)
    {
        if (max % i == 0)
        {
            if (OddIsPrime(i))  // i is odd
            {
                maxFactor = i;
            }
        }
    }
    Console.WriteLine(maxFactor.ToString());
    Console.ReadLine();
}
于 2012-08-19T09:17:21.307 回答
3

您应该在找到每个因素时对其进行划分。那么就不需要测试它们的素数了，当我们按升序枚举可能的除数时（任何这样找到的除数都不能是复合的，它的因子已经被除掉了）。然后您的代码变为：

class LargestPrimeFactor4 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;   // odd value is not divided by any even
        long pFactor = 1L;

        start = System.currentTimeMillis();

        for(long i = 3L; i <= num / i; ) 
        {
            if( num % i == 0 ) {
                pFactor = i;
                num = num / i;
            }
            else {
                i += 2;
            }
        }
        if( pFactor < num ) { pFactor = num; }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println( pFactor + " Time: " + totalTime);
    }
}
于 2012-08-20T22:30:24.833 回答
2 
public HashSet<Integer> distinctPrimeFactors(int n) //insane fast prime factor generator
{
    HashSet<Integer> factors = new HashSet<Integer>();
    int lastres = n;
    if (n==1)
    {
        factors.add(1);
        return factors;
    }
    while (true)
    {
        if (lastres==1)
            break;
        int c = 2;
        while (true)
        {
            if (lastres%c==0)
                break;
            c++;
        }
        factors.add(c);
        lastres/=c;
    }
    return factors;
}

如果您想为一个数字快速生成不同的素因子，请使用此方法，这会使每次迭代的数字更小。您可以将 int 更改为 long，它应该适合您。

于 2012-08-19T09:16:34.113 回答
1

这是通过试除法进行整数分解的伪代码：

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    output n

理解这一点的最简单方法是举个例子。考虑 n = 13195 的因式分解。最初 z = 2，但 13195 除以 2 余数为 1，因此 else 子句设置 z = 3 并循环。现在 n 不能被 3 或 4 整除，但是当 z = 5 时，13195 除以 5 的余数为零，因此输出 5 并将 13195 除以 5，因此 n = 2639 和 z = 5 不变。现在新的 n = 2639 不能被 5 或 6 整除，但可以被 7 整除，所以输出 7 并设置 n = 2639 / 7 = 377。现在我们继续 z = 7，留下余数，除法也是乘以 8、9、10、11、12，但 377 / 13 = 29 没有余数，所以输出 13 并设置 n = 29。此时 z = 13，且 z * z = 169，即大于 29，所以 29 是素数，是 13195 的最终因数，所以输出 29。完整的因式分解为 5 * 7 * 13 * 29 = 13195。

有更好的整数因式分解算法使用试除法，甚至更强大的整数分解算法使用除试除法以外的技术，但上面显示的算法将帮助您入门，并且对于 Project Euler #3 来说已经足够了。当您准备好更多时，请看这里。

于 2012-08-19T14:07:53.163 回答
0

提高性能的两件事：

static boolean isPrime(long n)
{
    for(int i = 2; i <= sqrt(n); i++)  // if n = a * b, then either a or b must be <= sqrt(n).
    {
        if(n % i == 0)
        {
            return false;
        }
    }        
    return true;
}

现在进入主循环

for(int i = num; i > 1; i--) // your interested in the biggest, so search from high to low until you have a match
{
    if(num % i == 0 && isPrime(i)) // check for num % i == 0 is faster, so do this first
    {
        pFactor = i;
        break; // break if you have a factor, since you've searched from the top
    }
}

这里仍有一些可以改进的地方，但那是你自己去发现的。想着修改num。玩得开心项目 Euler :)

于 2012-08-19T09:12:47.600 回答
0

您可以只对数字进行质因数分解，然后最大的质因数就是答案：

import java.util.ArrayList;
import java.util.Collections;

public class PrimeFactorization {

    /* returns true if parameter n is a prime number, 
         false if composite or neither */
    public static boolean isPrime(long n) {
        if (n < 2) return false;
        else if (n == 2) return true;
        for (int i = 2; i < Math.pow(n, 0.5) + 1; i++)
            if (n % i == 0)
                return false;
        return true;
    }

    /* returns smallest factor of parameter n */
    public static long findSmallestFactor(long n) {
        int factor = 2; // start at lowest possible factor
        while (n % factor != 0) { // go until factor is a factor
            factor++; // test the next factor
        }
        return factor;
    }

    /* reduces the parameter n into a product of only prime numbers
       and returns a list of those prime number factors */
    public static ArrayList<Long> primeFactorization(long n) {

        ArrayList<Long> primes = new ArrayList<Long>();
          // list of prime factors in the prime factorization
        long largestFactor = n / findSmallestFactor(n);    

        long i = 2;
        while (i <= largestFactor) { 
          // for all possible prime factors 
          // (2 - largest factor of the number being reduced)

            if (isPrime(i) && n % i == 0) { 
                // if this value is prime and the number is divisible by it

                primes.add(i); // add that prime factor to the list
                n /= i; // divide out that prime factor from the number 
                        // to start reducing the new number
                largestFactor /= i; // divide out that prime factor 
                       // from the largest factor to get the largest 
                       // factor of the new number
                i = 2; // reset the prime factor test
            } else {
                i++; // increment the factor test
            }
        }

        primes.add(n); // add the last prime number that could not be factored
        Collections.sort(primes);
        return primes;
    }
}

然后这样称呼它：

ArrayList<Long> primes = PrimeFactorization.primeFactorization(600851475143L);
System.out.println(primes.get(primes.size() - 1));

整个过程只需要几毫秒。

于 2014-05-11T07:11:05.937 回答
0

这不是完美的解决方案，但它适用于 600851475143。

public static void main(String[] args) {
    long number= 600851475143L;
    int rootOfNumber = (int)Math.sqrt(number)+10;
    for(int i = rootOfNumber; i > 2; i--) {
        if(number % i == 0) {
            if(psudoprime(i)) {
                System.out.println(i);
                break;
            }
        }
    }

}

public static boolean psudoprime(int num) {
    for(int i = 2; i < 100; i++) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}
于 2017-12-26T16:39:10.793 回答
-1 
public class LargestPrimeFactor {
    static boolean isPrime(long n){
        for(long i=2;i<=n/2;i++){
            if(n%i==0){
                return false;                                               
            }
        }
        return true;    
    }

    static long LargestPrimeFact(long n){
        long largestPrime=0;
        for(long i=2;i<Math.sqrt(n)/2;i++){
            if(n%i==0){
                if(isPrime(i)){
                    largestPrime=i;
                }
                }                                       
            }
        return largestPrime;
    }
    public static void main(String args[]) {
        System.out.println (LargestPrimeFact(600851475143L));
    }
}

资料来源： http ://crispylogs.com/project-euler-problem-3-solution/

于 2014-05-11T05:45:11.933 回答
-1

这个完美的工作！

public class Puzzle3 {
public static void main(String ar[])
{
    Long i=new Long("1");
    Long p=new Long("600851475143");
    Long f=new Long("1");
    while(p>=i)
    {
        if(p%i==0)
        {
            f=i;
            p=p/i;
            int x=1;
            i=(long)x;
        }
        i=i+2;
    }
    System.out.println(f);
}

}

于 2014-08-11T13:14:13.767 回答