## oschvr

### a blog about software, cloud computing, security, money, business, travelling and life.

**← Problems**

# Largest prime factor

#### 1 min

#### over 1 year ago

###### 02/05/2019

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

What is the largest prime factor of the number 600851475143 ?

We neeed to find the largest prime factor of **600851475143**.

We know that the largest prime factor of a number, its the number itself.

As a concept refresher, any **prime number** is only divisible by 1 ant itself, thus, when dividing by a certain number, there should not be a reminder.

2 is the first prime number, and holds the honor of being the only even prime numnber.

We'll start by making a function to return a `bool`

if the former condition holds.

```
func isPrime(x
int64) bool {
var i int64 = 2 // We start with 2 as it is the first prime number
for ; i < x; i++ {
if x % i == 0 {
return false
}
}
return true
}
```

Next, we need to test factors and see if they are prime numbers. Let's state:

$$ ab = N space where space 1 < a leq b leq N $$

$$ N = ab geq a^2 Leftrightarrow a^2 leq N Rightarrow sqrt[]{N} $$

This means that in order to test the primality of a composite number N, you check if this number is a product of two numbers. Thus we use square root.

```
package main
import (
"fmt"
"math"
"time"
)
const n int64 = 600851475143
func isPrime(x int64) bool {
var i int64 = 2
for i < x; i++ {
if x%i == 0 {
return false
}
}
return true
}
func
main() {
start := time.Now()
var i = int64(math.Sqrt(float64(n)))
for ;
i > 1; i-- {
if n % i == 0 && isPrime(i) {
fmt.Println("Execution time: ", time.Since(start))
fmt.Println("Largest Prime Factor: ", i)
break
}
}
}
```

Execution time: *7.990898ms*

Answer:
Largest Prime Factor: **6857**