Given a number N, the task is to find the largest prime factor of that number.
 Example 1:
Input:
N = 5
Output:
5
Explanation:
5 has 1 prime factor i.e 5 only.
Example 2:
Input:
N = 24
Output:
3
Explanation:
24 has 2 prime factors 2 and 3 in which 3 is greater.
Your Task:
You don't need to read input or print anything. Your task is to complete the function largestPrimeFactor() which takes an integer N as input parameters and returns an integer, largest prime factor of N.
Expected Time Complexity: O(sqrt(N))
Expected Space Complexity: O(1)
Constraints:
2 <= N <= 10^{9}

Difficulty: MEDIUM
Tags: Number theory

Mathematics
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def largestPrimeFactor (self, N):

        # code here

        

Solutions:
class Solution:

	def isprime(self, n):
		if n == 1:
			return False
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

	def largestPrimeFactor(self, N):
		for i in range(N, 1, -1):
			if N % i == 0 and self.isprime(i):
				return i
				break


class Solution:

	def largestPrimeFactor(self, N):

		def prime_check(a):
			primes = [1] * (a + 1)
			primes[0] = 1
			primes[1] = 0
			for i in range(2, a + 1):
				if primes[i] == 1:
					for j in range(i + i, a + 1, i):
						primes[j] = 0
			if primes[a] == 1:
				return True
			return False
		if prime_check(N):
			return N
		op = []
		for i in range(1, N // 2 + 1):
			if N % i == 0 and prime_check(i):
				op.append(i)
		return op[-1]


import math

def pmn(x):
	y = int(math.sqrt(x))
	for i in range(2, y + 1):
		if x % i == 0:
			return 0
	return 1

class Solution:

	def largestPrimeFactor(self, N):
		if pmn(N) == 1:
			return N
		for i in range(N // 2, 0, -1):
			if N % i == 0:
				if pmn(i) == 1:
					return i


from math import *

class Solution:

	def largestPrimeFactor(self, N):
		p = [1] * 10 ** 5
		p[0] = 0
		p[1] = 0
		sq = int(sqrt(N))
		for i in range(2, sq + 1):
			if p[i] == 1:
				for j in range(i * i, 10 ** 5, i):
					p[j] = 0
		for i in range(2, N + 1):
			if p[i] and N % i == 0:
				m = i
		return m


def isprime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True

class Solution:

	def largestPrimeFactor(self, N):
		maxi = 0
		for i in range(1, N + 1):
			if N % i == 0:
				if isprime(i):
					maxi = max(i, maxi)
		return maxi


import math

class Solution:

	def isPrime(self, x):
		if x < 2:
			return False
		for i in range(2, int(x ** 0.5 + 1)):
			if x % i == 0:
				return False
		return True

	def largestPrimeFactor(self, N):
		ans = 0
		for i in range(2, N + 1):
			if N % i == 0:
				if self.isPrime(i) == True:
					ans = i
		return ans


class Solution:

	def largestPrimeFactor(self, N):
		l = []
		for i in range(2, N + 1):
			if N % i == 0:
				for j in range(2, i // 2 + 1):
					if i % j == 0:
						break
				else:
					l.append(i)
		return max(l)


import math

class Solution:

	def largestPrimeFactor(self, N):
		list = []
		for i in range(2, N + 1):
			if N % i == 0:
				flag = 0
				for j in range(2, i):
					if i % j == 0:
						flag = 1
						break
				if flag == 0:
					list.append(i)
		return max(list)


class Solution:

	def checkprime(self, N):
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				return False
		return True

	def largestPrimeFactor(self, N):
		l = []
		for i in range(2, N + 1):
			if N % i == 0 and self.checkprime(i):
				l.append(i)
		return max(l)


import math

class Solution:

	def largestPrimeFactor(self, N):
		if N <= 2:
			return N
		largest = 1
		if N % 2 == 0:
			while N % 2 == 0:
				largest = 2
				N = N // 2
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			if N % i == 0:
				while N % i == 0:
					largest = i
					N = N // i
		if N > 2:
			return N
		return largest


class Solution:

	def largestPrimeFactor(self, N):

		def isPrime(n):
			if n == 1:
				return False
			if n == 2 or n == 3:
				return True
			if n % 2 == 0 or n % 3 == 0:
				return False
			i = 5
			while i * i <= n:
				if n % i == 0 or n % (i + 2) == 0:
					return False
				i += 6
			return True
		for i in range(N, 0, -1):
			if N % i == 0:
				if isPrime(i):
					return i


import math

class Solution:

	def largestPrimeFactor(self, N):
		k = 0
		while N % 2 == 0:
			N = N // 2
			k = 2
		i = 3
		while i <= math.floor(math.sqrt(N)):
			if N % i == 0:
				k = i
				N = N // i
			else:
				i += 1
		if N > 2 and N > k:
			k = N
		return k


class Solution:

	def largestPrimeFactor(self, N):
		a = []
		i = 2
		while i <= N:
			while N % i == 0:
				a.append(i)
				N = N / i
			i = i + 1
		return max(a)


class Solution:

	def largestPrimeFactor(self, N):
		arr = [1] * (N + 1)
		ans = 2
		for i in range(2, N + 1):
			if arr[i] == 1:
				if N % i == 0:
					ans = i
				for j in range(i * i, N + 1, i):
					arr[j] = 0
		return ans


class Solution:

	def largestPrimeFactor(self, N):
		n = 1
		while N > 1:
			d = self.getNextLargestFactor(N)
			n = max(d, n)
			N = int(N / d)
		return n

	def getNextLargestFactor(self, n):
		if n % 2 == 0:
			return 2
		for i in range(3, int(n ** 0.5) + 1):
			for j in range(2, i):
				if i % j == 0:
					break
				if j == i - 1 and n % (j + 1) == 0:
					return j + 1
		return n


class Solution:

	def prime(self, n):
		c = 0
		for i in range(2, n + 1):
			if n % i == 0:
				c += 1
			if c > 1:
				break
		if c == 1:
			return 1
		else:
			return 0

	def largestPrimeFactor(self, N):
		res = []
		for i in range(1, N + 1):
			if N % i == 0:
				if self.prime(i):
					res.append(i)
		return max(res)


import math

class Solution:

	def largestPrimeFactor(self, N):
		maxi = 2
		num = N
		for i in range(2, int(math.sqrt(N)) + 1):
			while num % i == 0:
				num /= i
				maxi = i
		if num > 2:
			return int(num)
		else:
			return maxi


class Solution:

	def largestPrimeFactor(self, N):
		l = []
		k = []
		for i in range(1, N + 1):
			if N % i == 0:
				l.append(i)
		for i in l:
			x = Solution.checkPrime(self, i)
			if x == 1:
				k.append(i)
		return max(k)

	def checkPrime(self, N):
		count = 0
		for i in range(2, N):
			if N % i == 0:
				count += 1
		if count == 0:
			return 1
		else:
			return 0


class Solution:

	def sieveOfEratosthenes(self, N):
		prime = [True for i in range(N + 1)]
		p = 2
		while p * p <= N:
			if prime[p]:
				for i in range(p * p, N + 1, p):
					prime[i] = False
			p += 1
		ans = []
		for i in range(2, N + 1):
			if prime[i]:
				ans.append(i)
		for i in range(len(ans) - 1, -1, -1):
			if N % ans[i] == 0:
				return ans[i]

	def largestPrimeFactor(self, N):
		return self.sieveOfEratosthenes(N)


class Solution:

	def largestPrimeFactor(self, N):
		i = 2
		res = []
		while i <= N:
			if N % i == 0:
				res.append(i)
				N //= i
			else:
				i += 1
		return max(res)


class Solution:

	def largestPrimeFactor(self, N):
		l = []
		for i in range(2, N + 1):
			if N % i == 0:
				flag = 0
				for j in range(2, i):
					if i % j == 0:
						flag = 1
				if flag == 0:
					l.append(i)
		l = sorted(l)
		return l[-1]


import math

class Solution:

	def largestPrimeFactor(self, n):
		x = []
		y = []

		def ip(n):
			c = 0
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					c = c + 1
			if c != 0 or (n == 1 or n == 0):
				return False
			else:
				return True
		for i in range(1, n + 1):
			if n % i == 0:
				x.append(i)
		for j in x:
			if ip(j) == True:
				y.append(j)
		return max(y)


import math

class Solution:

	def largestPrimeFactor(self, N):
		l = []
		p = []
		x = [True] * (N + 1)
		x[0] = False
		x[1] = False
		z = int(math.sqrt(N))
		for i in range(2, z + 1):
			if x[i]:
				for j in range(i + i, N + 1, i):
					x[j] = False
		for i in range(len(x)):
			if x[i] == True:
				l.append(i)
		for i in l:
			if N % i == 0:
				p.append(i)
		q = max(p)
		return q


class Solution:

	def largestPrimeFactor(self, N):

		def prime(n):
			flag = True
			for i in range(2, n):
				if n % i == 0:
					flag = False
					break
			return flag
		a = 0
		for j in range(2, N + 1):
			if N % j == 0:
				res = prime(j)
				if res:
					a = j
		return a


class Solution:

	def largestPrimeFactor(self, N):
		import math

		def is_prime(n):
			if n < 2:
				return False
			s = int(math.sqrt(n))
			for i in range(2, s + 1):
				if n % i == 0:
					return False
			return True
		l = []
		for i in range(1, N + 1):
			if N % i == 0:
				l.append(i)
		a = []
		for j in l:
			if is_prime(j) == True:
				a.append(j)
		return max(a)


class Solution:

	def largestPrimeFactor(self, N):
		for i in range(2, N + 1):
			if N % i == 0:
				f = 0
				for j in range(1, i + 1):
					if i % j == 0:
						f += 1
				if f == 2:
					pf = i
		return pf


class Solution:

	def largestPrimeFactor(self, N):

		def prime(n):
			if n == 1 or n == 0:
				return 0
			k = int(n ** 0.5)
			for i in range(2, k + 1):
				if n % i == 0:
					return 0
			return 1
		l = []
		for i in range(1, N + 1):
			if N % i == 0 and prime(i):
				l.append(i)
		return max(l)


from math import sqrt

class Solution:

	def largestPrimeFactor(self, N):

		def prime(a):
			if a < 2:
				return False
			for i in range(2, int(sqrt(a)) + 1):
				if a % i == 0:
					return False
			return True
		l = []
		for j in range(2, N + 1):
			if N % j == 0 and prime(j) == True:
				l.append(j)
		return max(l)


import math

class Solution:

	def checkPrime(N):
		count = 0
		for i in range(1, int(math.sqrt(N)) + 1):
			if N % i == 0:
				if i * i == N:
					count += 1
				else:
					count += 2
		if count == 2:
			return 1
		return 0

	def largestPrimeFactor(self, N):
		maxPrime = 2
		if Solution.checkPrime(N):
			return N
		for i in range(1, int(math.sqrt(N)) + 1):
			x = N // i
			if N % i == 0 and Solution.checkPrime(i):
				if i >= maxPrime:
					maxPrime = i
			if i * i != N and N % x == 0 and Solution.checkPrime(x):
				if x >= maxPrime:
					maxPrime = x
		return maxPrime


import math

class Solution:

	def largestPrimeFactor(self, N):
		l = []

		def prime(x):
			if x < 2:
				return False
			for i in range(2, int(math.sqrt(x)) + 1):
				if x % i == 0:
					return False
			return True
		for i in range(1, N + 1):
			if N % i == 0 and prime(i):
				l.append(i)
		return l[-1]


class Solution:

	def largestPrimeFactor(self, N):
		a = []
		for i in range(1, N + 1):
			if N % i == 0:
				for j in range(2, int(i ** 0.5) + 1):
					if i % j == 0:
						break
				else:
					a.append(i)
		return max(a)


class Solution:

	def largestPrimeFactor(self, n):
		import math

		def prime(n):
			c = 0
			k = int(math.sqrt(n))
			for i in range(2, k + 1):
				if n % i == 0:
					c += 1
			if c == 0:
				return True
		l = []
		for i in range(2, n + 1):
			if n % i == 0 and prime(i):
				l.append(i)
		return max(l)


import math

def isprime(N):
	if N < 2:
		return 0
	s = int(math.sqrt(N))
	for i in range(2, s + 1):
		if N % i == 0:
			return 0
	return 1

class Solution:

	def largestPrimeFactor(self, N):
		primeFactors = []
		for num in range(2, N // 2 + 1):
			if N % num == 0 and isprime(num):
				primeFactors.append(num)
		if isprime(N):
			primeFactors.append(N)
		return max(primeFactors)


import math

class Solution:

	def largestPrimeFactor(self, ub):
		seive = [True] * (ub + 1)
		seive[0] = False
		seive[1] = False
		s = int(math.sqrt(ub))
		for i in range(2, s + 1):
			for j in range(i + i, ub + 1, i):
				seive[j] = False
		l = []
		k = []
		for i in range(len(seive)):
			if seive[i] == True:
				l.append(i)
		for i in l:
			if ub % i == 0:
				k.append(i)
		return max(k)


class Solution:

	def largestPrimeFactor(self, N):
		tmp = N
		i = 2
		maxm = float('-inf')
		while i * i <= tmp:
			large = 0
			while N % i == 0:
				N = N // i
				if i >= large:
					large = i
			maxm = max(maxm, large)
			i += 1
		if N != 1:
			maxm = max(maxm, N)
		return maxm


class Solution:

	def largestPrimeFactor(self, N):
		a = [True for i in range(N + 1)]
		p = 2
		while p * p <= N:
			if a[p]:
				for i in range(p * p, N + 1, p):
					a[i] = False
			p += 1
		m = 1
		for i in range(2, N + 1):
			if a[i] and N % i == 0:
				m = max(1, 2, i)
		return m


import math

def isprime(n):
	if n <= 1:
		return 0
	s = int(math.sqrt(n))
	for i in range(2, s + 1):
		if n % i == 0:
			return 0
	return 1

class Solution:

	def largestPrimeFactor(self, N):
		a = []
		for i in range(1, N // 2 + 1):
			if N % i == 0 and isprime(i) == 1:
				a.append(i)
		if isprime(N):
			a.append(N)
		c = max(a)
		return c


import math

def isPrime(N):
	c = 0
	if N < 2:
		return False
	s = int(math.sqrt(N))
	for i in range(2, s + 1):
		if N % i == 0:
			c = c + 1
	if c == 0:
		return True
	else:
		return False

class Solution:

	def largestPrimeFactor(self, N):
		k = []
		for i in range(1, N + 1):
			if N % i == 0:
				if isPrime(i):
					k.append(i)
		return max(k)


import math

class Solution:

	def largestPrimeFactor(self, N):
		n = N
		lst = []
		k = []
		l = [True] * (n + 1)
		l[0] = l[1] = False
		s = int(math.sqrt(n))
		for i in range(2, s + 1):
			if l[i]:
				for j in range(i + i, n + 1, i):
					l[j] = False
		for i in range(len(l)):
			if l[i]:
				lst.append(i)
		for i in lst:
			if n % i == 0:
				k.append(i)
		return max(k)


import math

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

class Solution:

	def largestPrimeFactor(self, N):
		x = []
		for i in range(2, N + 1):
			if N % i == 0:
				if isPrime(i) == True:
					x.append(i)
		return max(x)


import math

def prime(n):
	if n < 2:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

class Solution:

	def largestPrimeFactor(self, N):
		d = []
		for i in range(1, N + 1):
			if N % i == 0 and prime(i):
				d.append(i)
		return max(d)


class Solution:

	def largestPrimeFactor(self, N):
		c = []

		def isprime(n):
			if n < 2:
				return 0
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return 0
			return 1
		for i in range(1, N + 1):
			if N % i == 0 and isprime(i):
				c.append(i)
		return max(c)


class Solution:

	def largestPrimeFactor(self, n):
		x = 2
		while x < n:
			if n % x == 0:
				n = n // x
			else:
				x = x + 1
		return n


import math

def is_prime(n):
	if n < 2:
		return False
	s = int(math.sqrt(n))
	for i in range(2, s + 1):
		if n % i == 0:
			return False
	return True

class Solution:

	def largestPrimeFactor(self, N):
		import math
		lst = []
		s = int(N / 2)
		for i in range(2, s + 1):
			if N % i == 0 and is_prime(i) == True:
				lst.append(i)
		if len(lst) != 0:
			return max(lst)
		else:
			return N


import math

class Solution:

	def largestPrimeFactor(self, N):
		sieve = [True] * (N + 1)
		sieve[0] = False
		sieve[1] = False
		sq = int(math.sqrt(N))
		for i in range(2, sq + 1):
			if sieve[i]:
				for j in range(i + i, N + 1, i):
					if j % i == 0:
						sieve[j] = False
		for k in range(len(sieve) - 1, 0, -1):
			if N % k == 0 and sieve[k]:
				return k


import math as m

class Solution:

	def largestPrimeFactor(self, N):
		seive = [True] * (N + 1)
		seive[0] = seive[1] = False
		for i in range(2, m.ceil(m.sqrt(N)) + 1):
			if seive[i]:
				for j in range(i + i, len(seive), i):
					seive[j] = False
		max = 0
		for i in range(2, N + 1):
			if N % i == 0:
				if i > max and seive[i] == True:
					max = i
		return max


class Solution:

	def largestPrimeFactor(self, N):

		def prime(n):
			if n < 2:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		s = 0
		for i in range(1, N + 1):
			if N % i == 0 and prime(i):
				if s < i:
					s = i
		return s


class Solution:

	def largestPrimeFactor(self, N):

		def prime(n):
			if n < 2:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		v = []
		for i in range(1, N + 1):
			if N % i == 0 and prime(i):
				v.append(i)
		return max(v)


import math

class Solution:

	def largestPrimeFactor(self, N):
		l = []

		def prime(r):
			f = 0
			if r == 1:
				f = 1
			for i in range(2, int(math.sqrt(r)) + 1):
				if r % i == 0:
					f = 1
					break
			return f
		for i in range(2, N + 1):
			if N % i == 0 and prime(i) == 0:
				l.append(i)
		return max(l)


import math

class Solution:

	def largestPrimeFactor(self, N):

		def isprime(N):
			if N == 0 or N == 1:
				return 0
			else:
				for i in range(2, int(math.sqrt(N)) + 1):
					if N % i == 0:
						return 0
				return 1
		l = []
		for i in range(1, N + 1):
			if N % i == 0:
				if isprime(i) == 1:
					l.append(i)
		return max(l)


import math

def isprime(c):
	if c < 2:
		return False
	for i in range(2, int(math.sqrt(c)) + 1):
		if c % i == 0:
			return False
	return True

class Solution:

	def largestPrimeFactor(self, N):
		for i in range(1, N + 1):
			if N % i == 0 and isprime(i) == True:
				c = i
		return c


class Solution:

	def largestPrimeFactor(self, n):
		prime = [1] * (n + 1)
		for i in range(2, n + 1):
			if prime[i] == 1:
				prime[i] = i
				for j in range(i, n + 1, i):
					prime[j] = i
		return prime[n]


class Solution:

	def largestPrimeFactor(self, N):
		c = 2
		k = []
		while N > 1:
			if N % c == 0:
				k.append(c)
				N //= c
			else:
				c += 1
		return max(k)


X = int(100000.0)
primes = [1] * (X + 1)
primes[0] = primes[1] = 0
for i in range(2, int(X ** 0.5) + 1):
	if primes[i]:
		for j in range(i * i, X + 1, i):
			primes[j] = 0

class Solution:

	def largestPrimeFactor(self, N):
		prime_factors = []
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0:
				if primes[i]:
					prime_factors.append(i)
				if primes[N // i]:
					prime_factors.append(N // i)
		return max(prime_factors)


class Solution:

	def largestPrimeFactor(self, n):
		largest_prime = -1
		i = 2
		while i * i <= n:
			while n % i == 0:
				largest_prime = i
				n = n // i
			i = i + 1
		if n > 1:
			largest_prime = n
		return largest_prime


class Solution:

	def largestPrimeFactor(self, N):
		from math import floor, sqrt
		M = N + 1
		primes = [True] * M
		primes[0] = primes[1] = False
		ans = 1
		for i in range(2, M):
			if not primes[i]:
				continue
			if N % i == 0:
				ans = i
			for j in range(i * i, M, i):
				primes[j] = False
		return ans if ans > 1 else N


class Solution:

	def largestPrimeFactor(self, N):
		c = 0

		def mani(i):
			if i == 1:
				return 0
			if i == 2:
				return 1
			for j in range(2, int(i ** 0.5) + 1):
				if i % j == 0:
					return 0
			return 1
		for i in range(1, N + 1):
			if N % i == 0:
				if mani(i) == 1:
					c = i
		return c


import math

class Solution:

	def largestPrimeFactor(self, N):
		num = 2
		while num <= math.sqrt(N):
			if N % num == 0:
				N = N // num
			else:
				num += 1
		return int(N)


from math import sqrt

class Solution:

	def largestPrimeFactor(self, n):
		maxPrime = -1
		while n % 2 == 0:
			maxPrime = 2
			n /= 2
		while n % 3 == 0:
			maxPrime = 3
			n /= 3
		for i in range(5, int(sqrt(n)) + 1, 6):
			while n % i == 0:
				maxPrime = i
				n /= i
			while n % (i + 2) == 0:
				maxPrime = i + 2
				n /= i + 2
		if n > 4:
			maxPrime = n
		return int(maxPrime)


import sys

class Solution:

	def largestPrimeFactor(self, N):
		maxi = -sys.maxsize
		for i in range(2, N + 1):
			while N % i == 0:
				N //= i
				maxi = max(maxi, i)
		return maxi


class Solution:

	def largestPrimeFactor(self, N):
		i = 2
		res = -1
		while i <= N:
			while N % i == 0:
				N //= i
				res = i
			i += 1
		return res


class Solution:

	def largestPrimeFactor(self, N):
		isPrime = [True] * (N + 1)
		for i in range(2, int(N ** 0.5) + 1):
			if isPrime[i] == False:
				continue
			for j in range(i * i, N + 1, i):
				isPrime[j] = False
		for i in range(N, 1, -1):
			if N % i == 0 and isPrime[i]:
				return i
		return N


class Solution:

	def largestPrimeFactor(self, N):

		def checkPrime(N):
			if N < 2:
				return False
			for i in range(2, N):
				if N % i == 0:
					return False
			return True
		max_prime = 0
		for i in range(1, int(N ** (1 / 2)) + 1):
			if N % i == 0:
				if checkPrime(i):
					max_prime = max(max_prime, i)
				if checkPrime(N // i):
					max_prime = max(max_prime, N // i)
		return max_prime


class Solution:

	def largestPrimeFactor(self, n):
		maxi = 2
		c = 2
		while n > 1:
			if n % c == 0:
				maxi = max(maxi, c)
				n = n / c
			else:
				c += 1
		return maxi


class Solution:

	def largestPrimeFactor(self, N):
		i = 2
		while N > 1:
			if N % i == 0:
				N = int(N / i)
			else:
				i = i + 1
		return i


import math

class Solution:

	def largestPrimeFactor(self, n):

		def isPrime(n):
			if n == 0 or n == 1:
				return False
			else:
				lim = int(math.sqrt(n)) + 1
				for i in range(2, lim):
					if n % i == 0:
						return False
				return True
		lim = int(math.sqrt(N)) + 1
		m = -1 * (10 ** 9 + 7)
		for i in range(1, lim):
			if n % i == 0:
				if isPrime(i):
					m = max(m, i)
				if isPrime(n // i):
					m = max(n // i, m)
		return m


import math

class Solution:

	def largestPrimeFactor(self, n):
		l = []
		if n == 0:
			return None
		while n % 2 == 0:
			l.append(2)
			n = n / 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				l.append(i)
				n = n / i
		if n > 2:
			l.append(n)
		return int(max(l))


class Solution:

	def largestPrimeFactor(self, N):
		factors = []
		for i in range(1, N + 1):
			if N % i == 0:
				factors.append(i)
		prime = []
		for i in factors:
			c = 0
			for j in range(1, i):
				if i % j == 0:
					c += 1
			if c == 1:
				prime.append(i)
		k = max(prime)
		return k