java - 欧拉计划#3

Question

问题：

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

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

我发现这个很容易，但是运行文件花了很长时间，它已经持续了一段时间，我得到的最高数字是 716151937。

这是我的代码，我只是要等待还是我的代码中有错误？

        //User made class
public class Three
{   
        public static boolean checkPrime(long p)
        {
            long i;
            boolean prime = false;
        for(i = 2;i<p/2;i++)
        {
            if(p%i==0)
            {
                prime = true;
                break;
            }
        }
    return prime;
    }   

}

    //Note: This is a separate file
public class ThreeMain
{
    public static void main(String[] args)
        {
            long comp = 600851475143L;
            boolean prime;
            long i;
            for(i=2;i<comp/2;i++)
            {
                if(comp%i==0)
                {
                    prime = Three.checkPrime(i);
                    if(prime==true)
                    {
                        System.out.println(i);
                    }
                }
            }
        }       
}

Answer 1

You're headed in the right direction, but you've gone way past where you need to go and have a couple of mistakes along the way. You're currently checking much higher than you need to verify primes (particularly primes >> 2). Your line: for(i = 2;i<p/2;i++) could be for(i = 2;i*i <= p;i++) (you need only check up to the square root of a number to determine if it's prime or composite).

Your function to check for primes actually returns true for composites, not primes. You're code:

    if ((p%i==0) {
        prime = true;
        break; }

should be

    if ((p%i==0) {
        prime = false;
        break; }

In your main method, you don't actually need the boolean prime at all. From the context of the question, we can assume that there will be more than two prime factors, which means the largest prime factor we need to reduce comp to a smaller and more manageable number is the cube root of comp. Therefore, your line for(i=2;i<comp/2;i++) could be for(i=2;i*i*i<comp;i++). Instead of continually checking if i divides comp and then checking if i is prime, you can reduce the size of comp by dividing by i until comp is not divisible by i anymore (to check for powers of i). Because you're starting with small values of i then you will never get a composite number that divides comp if you reduce it by i each time. When you've reduced comp to 1 then the current i will be the greatest prime factor and your answer to the problem.

Also, you're lines:

    prime = Three.checkPrime(i);
    if(prime==true)

can be reduced to:

if (Three.checkPrime(i));

because Three.checkPrime() will return, and ultimately be evaluated as, a boolean value.

Answer 2

一旦你找到了你的数字的一个因素，你可以把它分开来使剩余的数字更小。

if (prime)
{
    System.out.println(i);

    // The factor may occur multiple times, so we need a loop.                
    do {
        comp /= i;
    } while (comp % i == 0);
}

这样做还可以保证无论何时i除以comp,i必须是素数，因为所有较小的素数都已被除掉，因此您可以删除素数检查：

for (i = 2; i < comp/2; i++)
{
    if (comp % i == 0)
    {
        System.out.println(i);

        do {
            comp /= i;
        } while (comp % i == 0);
    }
}

最后，您只需要检查i平方根，comp因为任何大于平方根的因子都必须伴随着小于平方根的因子。（即如果i*j == comp，其中之一i或j必须是<=的平方根comp）。

还有一些技巧可以应用，但这对于这个问题应该绰绰有余。

Answer 3

在这里，我正在编写两种不同的逻辑来解决这个问题。我很确定它工作得更快

第一个是

import java.util.ArrayList;
import java.util.List;

public class Problem3 {
public void hfactor(long num)
 {
  List<Long> ob =new ArrayList<Long>();
 long working =num;
  long current =2;
  while(working !=1)
   {boolean isprime = true;
    for(Long prime :ob)
    {
      if(current%prime == 0)
       { isprime =false;
         break;   
       }
    }
    if(isprime)
    {ob.add(current);
       if(working%current ==0)
       {
       working /=current;
        }
     } 

  current++;    
    }
    System.out.println(ob.get(ob.size()-1));
   }    


 public static void main(String[] args) {
  Problem3 ob1 =new Problem3();
  ob1.hfactor(13195);
  }
  }

其次是

public static void main(String[] args) {
    List <Long> ob = new ArrayList<Long>(); 
    List<Long> ob1 = new ArrayList<Long>();

    long num =13195;
    for(int i = 2; i<num; i++)
      {
       if (num%i ==0)
         ob.add((long) i);  
      }

    for (int i =0; i<ob.size(); i++)
        for(int j =2; j<ob.get(i); j++)
            {
             if (ob.get(i)%j ==0)
                {
                 ob.set(i, (long) 0);
                    }
             }
           for(int i =0; i<ob.size(); i++){
              if(ob.get(i)!=0)
              {
                 ob1.add(ob.get(i)); 
              } 


             }

        System.out.println(ob1.get(ob1.size()-1));



    }}

Answer 4

你的算法很慢。这是通过试除法分解整数的标准方法：

define factors(n)
    f = 2
    while f * f <= n
        if n % f == 0
            output f
            n /= f
        else
            f = f + 1
    output n

有更好的方法来分解整数；您可以在我的博客上的一篇文章中阅读其中的一些内容。但是这个算法对于 Project Euler #3 来说已经足够了，在几乎任何现代语言中都可以在不到一秒的时间内给出答案。

Answer 5

您可以简单地循环到sqrt(2)而不是n/2哪个会节省大量时间。