## oschvr

### a blog about software, programming, business, travelling and life.

**← Problems**

# Largest prime factor

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

`1 2 3 4 5 6 7 8 9`

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

`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31`

`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**