Finding largest prime number out of 600851475143?

Question

I'm trying to solve problem 3 from http://projecteuler.net. However, when I run thing program nothing prints out. What am I doing wrong? Problem: What is the largest prime factor of the number 600851475143 ?

public class project_3 
{
    public boolean prime(long x)   // if x is prime return true
    {
        boolean bool = false;

        for(long count=1L; count<x; count++)
        {
            if( x%count==0 )
            {
                bool = false;
                break;
            }
            else { bool = true; }
        }
        return bool;
    }

    public static void main(String[] args)
    {
        long ultprime = 0L;  // largest prime value
        project_3 object = new project_3();

        for(long x=1L; x <= 600851475143L; x++)
        {
            if( object.prime(x)==true )
            {
                ultprime = ((x>ultprime) ? x : ultprime);
            }
        }
        System.out.println(ultprime);
    }
}

Answer 1

Answer in Python in less than a second.

Since we are looking for the largest factor we need to start high and count down. The first one we find, we quit. We don't need all the factors. Just one. Since all primes greater than 3 are 6k+1 we can use that to speed the search.

Since no factor will be greater than sqrt(600851475143)+1 we start there and count down by 6. So 775147 down to 5.

To be sure we are using the 6(k) numbers we need to make the number we start with in the 6k+1 range So 6k+1 numbers mod 6 result in a remainder of 1 (7%6 = 1 and 13%6 = 1).

Our square root + 1 = 775147 works out! 775147%6 = 1 So we can start. Now we count down by 6 and check 6k+1 which will be i and i-2 which is 6k-1 all the way to 7. Then we check 3 and 2 as a last resort. If all this fails n is prime and we return that.

def is_prime(n):  
    if (n <= 3): return n > 1      
    if not (n%6 == 1 or n%6 == 5): return False      
    for p,q in ((i,i+2) for i in range(5,int(n**.5)+1,6)): 
        if (n%p == 0 or n%q == 0):  return False          
    return True  

def lpf(n):
    start = int(n**.5)+1
    if start%6 != 1: # 6k+1? 
        start = (n-5)+(n%6-((n%2)*2)) # make it 6k+1
    for p,q in ((i,i-2) for i in range(start,7,-6)): 
        if n % p == 0 and is_prime(p): 
               return p
        if n % q == 0 and is_prime(q): 
                return q
    if n%3 == 0: return 3
    if n%2 == 0: return 2
    return n # prime
    
n = 600851475143
print(f"largest Prime Factor of {n:,} is {lpf(n):,}") 
#n = 100004041
#print(f"largest Prime Factor of {n:,} is {lpf(n):,}") 

It takes a few hundredths of a second to get the answer:

$ time python3 largest_prime_factor.py 
largest Prime Factor of 600,851,475,143 is 6,857

real    0m0.047s
user    0m0.043s
sys     0m0.005s

Answer 2

Not only does your prime checking function always return false; even if it were functioning properly, your main loop does not seek the input number's factors at all, but rather just the largest prime smaller or equal to it. In pseudocode, your code is equivalent to:

foo(n):
    x := 0 ;
    foreach d from 1 to n step 1:
        if is_prime(d):          // always false
            x := d
    return x                     // always 0

is_prime(d):
    not( d % 1 == 0 )            // always false

But you don't need the prime checking function here at all. The following finds all factors of a number, by trial division:

factors(n):
    fs := []
    d  := 2
    while ( d <= n/d ):
        if ( n % d == 0 ): { n := n/d ; fs := append(fs,d) }
        else:              { d := d+1 }
    if ( n > 1 ): { fs := append(fs, n) }
    return fs

The testing for divisibility is done only up to the square root of the number. Each factor, as it is found, is divided out of the number being factorized, thus further reducing the run time. Factorization of the number in question runs instantly, taking just 1473 iterations.

By construction all the factors thus found are guaranteed to be prime (that's why no prime checking is needed). It is crucial to enumerate the possible divisors in ascending order for this to happen¹. Ascending order is also the most efficient, because any given number is more likely to have smaller prime factor than larger one. Enumerating the primes instead of odds, though not necessary, will be more efficient if you have an efficient way of getting those primes, to test divide by.

It is trivial to augment the above to find the largest factor: just implement append as

append(fs,d):
    return d

---

¹ because then for any composite divisor d of the original number being factorized, when we'll reach d, we will have already divided its prime factors out of the original number, and so the reduced number will have no common prime factors with it, i.e. d won't divide the reduced number even though it divides the original.

Answer 3

The whole point of Project Euler is that the most obvious approaches to finding the answer will take so long to compute that they aren't worth running. That way you learn to look for the less obvious, more efficient approaches.

Your approach is technically correct in terms of whether or not it is capable of computing the largest prime of some number. The reason you aren't seeing anything print out is that your algorithm is not capable of solving the problem quickly.

The way you've designed this, it'll take somewhere around 4,000,000 years to finish.

If you replaced the 600851475143 number with say 20 it would be able to finish fairly quickly. But you have the 600 billion number, so it's not that simple.

Answer 4

Two things:

1) You are starting count at 1 instead of 2. All integers are divisible by 1.

2) You are running an O(n^2) algorithm against a rather large N (or at least you will be once you fix point #1). The runtime will be quite long.