Project Euler #3 - to Sieve or not to Sieve
Published: 2023-11-04 19:29:12

> **Project Euler Series**
>
> This is a 3rd post of ongoing series based on [Project Euler](https://projecteuler.net/).
> You can check out the previous post [here](https://dev.to/fangcode/project-euler-2-does-fibonacci-have-a-tail-349j).
>
> **Disclaimer**
>
> This blogpost provides solution to the 2nd problem from Project Euler. If you want to figure out a solution yourself, go to the [Problem 3's page](https://projecteuler.net/problem=3) 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.

```kotlin
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 {% katex inline %} \sqrt{600851475143} {% endkatex %} (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.

```kotlin
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:

```kotlin
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 {% katex inline %}O(\sqrt{n}) {% endkatex %} complexity. Then, in the worst case scenario, we will perform a check for each factor which is {% katex inline %}\sqrt{n}{% endkatex %} times. Single primality check with our method is a {% katex inline %} O(\sqrt{m}) {% endkatex %} where {% katex inline %}m{% endkatex %} is a factor number. In the worst case scenario {% katex inline %} m = \sqrt{n} {% endkatex %}. Hence, single check is:
{% katex %}
O(\sqrt{\sqrt{n}}) = O(n^\frac{1}{4})
{% endkatex %}
and with that, the whole complexity is: 
{% katex %}
O(\sqrt{n} * n^\frac{1}{4}) = O(n^\frac{3}{4})
{% endkatex %}

## 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.