Project Euler SeriesThis is a 3rd post of ongoing series based on Project Euler.

You can check out the previous post here.

DisclaimerThis 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 and come back later :)

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

The ProblemThe 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:

and with that, the whole complexity is:

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

## Top comments (0)