## Largest prime factor

### Problem

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

What is the largest prime factor of the number 600851475143 ?

- By the fundamental theorem of arithmetic, every integer n > 1 has a unique factorization as a product of prime numbers.
- In other words, the theorem says that n = p_0 * p_1 * … * p_{m-1}, where each p_i > 1 is prime but not necessarily unique.
- Now if we take the number n and repeatedly divide out its smallest factor (which must also be prime), then the last
- factor that we divide out must be the largest prime factor of n. For reference, 600851475143 = 71 * 839 * 1471 * 6857.

Ans:- **6857**

Program for problem

import math

```
import math
def compute(n):
while True:
p = smallest_prime_factor(n)
if p < n:
n //= p
else:
return str(n)
# Returns the smallest factor of n, which is in the range [2, n]. The result is always prime.
def smallest_prime_factor(n):
assert n >= 2
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return i
return n
n=600851475143
print(compute(n))
```

The Programming problem from Hackerrank.com

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

What is the largest prime factor of a given number **N** ?

**Input Format**

First line contains **T** , the number of test cases. This is followed by **T** lines each containing an integer **N**.

**Constraints**

**1⩽T⩽10****10⩽N⩽ 10**^{12}

**Output Format**

For each test case, display the largest prime factor of **N** .

**Sample Input **

```
2
10
17
```

**Sample Output **

```
5
17
```

**Explanation **

- Prime factors of
**10**are**{2,5}**, largest is . - Prime factor of
**17**is**17**itself, hence largest is**17**.

**Solution:-**

**Steps:-**

1. User must first enter the value and store it in a variable.

2. The while loop is used and the factors of the integer are computed by using the modulus operator and checking if the remainder of the number divided by i is 0.

3. Then the factors of the integer are then again checked if the factor is prime or not.

4. If the factor of the integer has two factors, the factor is prime.

5. The prime factor of the integer which is largest or last one will be printed

```
import sys
import math
def compute(n):
while True:
p = smallest_prime_factor(n)
if p < n:
n //= p
else:
return str(n)
# Returns the smallest factor of n, which is in the range [2, n]. The result is always prime.
def smallest_prime_factor(n):
assert n >= 2
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return i
return n # n itself is prime
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
print(compute(n))
```