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⩽ 1012

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))