Project Euler #3

Question

Question:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

I found this one pretty easy, but running the file took an extremely long time, it's been going on for a while and the highest number I've got to is 716151937.

Here is my code, am I just going to have a wait or is there an error in my code?

        //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

Here i am writing two different logic to solne this problem . I am quite sure it work faster

First one is

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

Second is

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 2

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 3

Your algorithm is slow. Here's the standard way to factor an integer by trial division:

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

There are better ways to factor integers; you can read about some of them in an essay at my blog. But this algorithm is sufficient for Project Euler #3, delivering an answer in less than a second in most any modern language.

Answer 4

Once you've found a factor of your number, you can divide it out to make the remaining number smaller.

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

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

Doing this also guarantees that whenever i divides comp, i must be prime since all the smaller primes have already been divided out, so you can remove the prime check:

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

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

Finally, you only need to check i up to the square root of comp since any factor larger than the square root must be accompanied by one that's smaller than the square root. (i.e. if i*j == comp, one of i or j must be <= the square root of comp).

There are a few more tricks that can be applied, but this should be more than enough for this problem.

Answer 5

You can simply loop to sqrt(2) instead of n/2 which will save lots of time.