Project Euler #3 - to Sieve or not to Sieve

Project Euler Series

This is a 3rd post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 3rd problem from Project Euler. If you want to figure out a solution yourself, go to the Problem 3's page and come back later :)

The time has come to tackle prime numbers. Let's see what's the 3rd task.

The Problem

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

What is the largest prime factor of the number 600851475143 ?

Prime numbers

If you're here, then probably, it's not a secret for you what a prime number is. However, just to have a full picture, let's define it. It's a number greater than 1, and it has only two factors: 1 and itself.

Be cautious, because 2 is a prime number as well! Somehow, I tricked my brain into thinking it's not because it's even, ha! What a mistake...

Am I prime?

Determining if a number is prime is a fundamental problem in number theory and computer science. There are a few options, but we will focus on the simplest ones a trial division. At first, I thought about using a sieve algorithm, however after analysis, it would be slower and memory consuming. To be fair, it would be good choice for getting a list of primes, but not to test if one is.

Basic Trial Division

In order to figure out if given number is a prime one we can make sure it has no factors beyond 1 and itself.

private fun isPrime(value: Long): Boolean {
    if (value < 2L) return false

    val checkBoundary = sqrt(value.toDouble()).toInt()

    val isDividable = (2..checkBoundary).any {
        value.mod(it) == 0
    }

    return !isDividable
}

First of all, look at the type of an input. We know the number for which we do the calculation, so we could choose Int as we do this test for a number up to $\sqrt{600851475143}$ (from the problem's description) - below Int's limit. The Long type is here only to have less casting, because as you can see, the input is above Int's limit.

Next thing is to perform this test only on factors of the given number. What's more, we are looking for the biggest prime factor, that's why we can perform the test starting from the end of factors collection. This will decrease number of checks.

private fun getBiggestPrimeFactorOf(input: Long): Long {
    val checkBoundary = sqrt(input.toDouble()).toLong()

    val factors = (2..checkBoundary).filter {
        input.mod(it) == 0L
    }

    return factors
        .reversed()
        .first(::isPrime)
}

This code gives us correct answer:

val input = 600_851_475_143L
val solution = getBiggestPrimeFactorOf(input)
println(solution) // 6857

Complexity Analysis

Let's dive into determining time complexity.

First, we get list of factors and that's a $O(\sqrt{n})$ complexity. Then, in the worst case scenario, we will perform a check for each factor which is $\sqrt{n}$ times. Single primality check with our method is a $O(\sqrt{m})$ where $m$ is a factor number. In the worst case scenario $m = \sqrt{n}$ . Hence, single check is:

$$O(\sqrt{\sqrt{n}}) = O(n^\frac{1}{4})$$

and with that, the whole complexity is:

$$O(\sqrt{n} * n^\frac{1}{4}) = O(n^\frac{3}{4})$$

Conclusion

It was still quite an easy problem to solve. However, interesting for me was the realisation that the sieve algorithm is not a great choice and I needed some time to figure out why it took a few times longer for the sieve to determine the biggest prime factor than the simple division.