Given a number N. Find its unique prime factors in increasing order.
 
Example 1:
Input: N = 100
Output: 2 5
Explanation: 2 and 5 are the unique prime
factors of 100.
Example 2:
Input: N = 35
Output: 5 7
Explanation: 5 and 7 are the unique prime
factors of 35.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function AllPrimeFactors() which takes N as input parameter and returns a list of all unique prime factors of N in increasing order.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 
Constraints:
1 <= N  <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:
	def AllPrimeFactors(self, N):
		# Code here

Solutions:
N = 10 ** 6
primes = [0] * (N + 1)
primes[1] = 1
primes[0] = 1
for i in range(2, N + 1):
	if primes[i] == 0:
		for j in range(i + i, N + 1, i):
			primes[j] = 1
numbers = [i for i in range(len(primes)) if primes[i] == 0]

class Solution:

	def AllPrimeFactors(self, N):
		global numbers
		opt = []
		i = 0
		while N >= numbers[i]:
			if N % numbers[i] == 0:
				opt.append(numbers[i])
			i += 1
		return opt


class Solution:

	def AllPrimeFactors(self, N):
		d = 2
		lst = set()
		while True:
			if N % d == 0:
				lst.add(d)
				N //= d
			else:
				d += 1
			if N < d:
				break
		lst = list(lst)
		lst.sort()
		return lst


import math

class Solution(object):

	def AllPrimeFactors(self, N):
		(result, divisor) = ([], 2)
		while divisor * divisor <= N:
			if N % divisor == 0:
				result.append(divisor)
				while N % divisor == 0:
					N //= divisor
			else:
				divisor += 1
		if N != 1:
			result.append(N)
		return result


from math import sqrt
from math import ceil

class Solution:

	def AllPrimeFactors(self, N):
		if N == 1:
			return []
		N1 = N
		arr = []
		if N % 2 == 0:
			arr.append(2)
			while N % 2 == 0:
				N = N / 2
		for i in range(3, int(sqrt(N)) + 1, 2):
			if N % i == 0:
				arr.append(i)
				while N % i == 0:
					N = N / i
		if N > 2:
			arr.append(int(N))
		return arr


import heapq

class Solution:

	def AllPrimeFactors(self, n):
		ans = []
		num = 2
		for i in range(n):
			if n % num == 0:
				heapq.heappush(ans, num)
				n = n // num
			else:
				num += 1
			if n < num:
				break
		arr = []
		prev = -1
		for i in range(len(ans)):
			if ans[i] != prev:
				prev = ans[i]
				arr.append(ans[i])
		return arr


class Solution:

	def AllPrimeFactors(self, N):
		res = []
		if N % 2 == 0:
			res.append(2)
			while N % 2 == 0:
				N = N // 2
		for i in range(3, N + 1, 2):
			if N % i == 0:
				res.append(i)
				while N % i == 0:
					N = N // i
		return res


class Solution:

	def AllPrimeFactors(self, N):
		factors = []
		i = 2
		while i * i <= N:
			if N % i == 0:
				is_prime = True
				for j in range(2, int(i ** 0.5) + 1):
					if i % j == 0:
						is_prime = False
						break
				if is_prime:
					if i not in factors:
						factors.append(i)
					N //= i
					continue
			if i == 2:
				i += 1
			else:
				i += 2
		if N > 1:
			is_prime = True
			for j in range(2, int(N ** 0.5) + 1):
				if N % j == 0:
					is_prime = False
					break
			if is_prime:
				if N not in factors:
					factors.append(N)
		return factors


class Solution:

	def isPrime(self, n):
		if n == 2 or n == 3:
			return True
		if n == 1 or 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 = i + 6
		return True

	def AllPrimeFactors(self, N):
		if self.isPrime(N):
			return [N]
		primeFactors = set()
		i = 2
		while i * i <= N:
			while N % i == 0:
				primeFactors.add(i)
				N = N // i
			i += 1
		if N > 1:
			primeFactors.add(N)
		return list(sorted(primeFactors))


class Solution:

	def AllPrimeFactors(self, N):

		def isprime(num):
			if num == 2 or num == 3 or num == 5:
				return True
			for i in range(3, int(num ** (1 / 2) + 1), 2):
				if num % i == 0:
					return False
			return True
		ans = []
		if N % 2 == 0:
			ans.append(2)
		x = 3
		while x <= N:
			if N % x == 0 and isprime(x):
				ans.append(x)
			x = x + 2
		return ans


class Solution:

	def AllPrimeFactors(self, N):
		num = N
		divisor = 2
		lst = []
		while True:
			if num % divisor == 0:
				lst.append(divisor)
				num = num // divisor
			else:
				divisor = divisor + 1
			if num < divisor:
				break
		lst = set(lst)
		lst = list(lst)
		lst.sort()
		return lst


class Solution:

	def AllPrimeFactors(self, N):
		num = N
		divisor = 2
		lst = []
		while True:
			if num % divisor == 0:
				lst.append(divisor)
				num = num // divisor
			else:
				divisor = divisor + 1
			if num < divisor:
				break
		lst2 = []
		for unique in lst:
			if unique not in lst2:
				lst2.append(unique)
		return lst2


class Solution:

	def AllPrimeFactors(self, N):
		l = []
		if N <= 1:
			return l
		while N % 2 == 0:
			if len(l) == 0 or l[-1] != 2:
				l.append(2)
			N = N // 2
		while N % 3 == 0:
			if len(l) == 0 or l[-1] != 3:
				l.append(3)
			N = N // 3
		for i in range(5, int(N ** 0.5) + 1, 6):
			while N % i == 0:
				if len(l) == 0 or l[-1] != i:
					l.append(i)
				N = N // i
			while N % (i + 2) == 0:
				if len(l) == 0 or l[-1] != i + 2:
					l.append(i + 2)
				N = N // (i + 2)
		if N > 3:
			l.append(N)
		return l


class Solution:

	def AllPrimeFactors(self, N):
		primes = self.generate_primes(int(N ** 0.5) + 1)
		factors = []
		last_factor = None
		for p in primes:
			while N % p == 0:
				if p != last_factor:
					factors.append(p)
					last_factor = p
				N //= p
		if N > 1 and N != last_factor:
			factors.append(N)
		return factors

	def generate_primes(self, n):
		primes = []
		sieve = [True] * (n + 1)
		for p in range(2, n + 1):
			if sieve[p]:
				primes.append(p)
				for i in range(p * p, n + 1, p):
					sieve[i] = False
		return primes


class Solution:

	def AllPrimeFactors(self, N):
		i = 2
		arr = []
		num = N
		if N == 2:
			return [2]
		while i <= N:
			if N % i == 0:
				arr.append(i)
			while N % i == 0:
				N = N // i
			i += 1
		return arr


import math

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

class Solution:

	def AllPrimeFactors(self, N):
		d = []
		if fun(N):
			return [N]
		for i in range(1, N // 2 + 1):
			if N % i == 0 and fun(i):
				d.append(i)
		return d


from math import sqrt

class Solution:

	def AllPrimeFactors(self, N):
		lis = []
		s = int(sqrt(N)) + 1
		if N % 2 == 0:
			while N % 2 == 0:
				if 2 not in lis:
					lis.append(2)
				N = N // 2
		for i in range(3, s, 2):
			while N % i == 0:
				if i not in lis:
					lis.append(i)
				N = N // i
		if N > 2:
			lis.append(N)
		return lis


import math

class Solution:

	def AllPrimeFactors(self, N):
		dic = []
		lis = []
		while N > 1 & N % 2 == 0:
			dic.append(2)
			N //= 2
		for i in range(3, int(math.sqrt(N) + 1), 2):
			while N % i == 0:
				dic.append(i)
				N //= i
		if N > 2:
			dic.append(N)
		l = list(set(dic))
		l.sort()
		return l


import math

class Solution:

	def AllPrimeFactors(self, N):
		dic = {}
		lis = []
		while N > 1 & N % 2 == 0:
			if 2 in dic:
				dic[2] += 1
			else:
				dic[2] = 1
			N //= 2
		for i in range(3, int(math.sqrt(N) + 1), 2):
			while N % i == 0:
				if i in dic:
					dic[i] += 1
				else:
					dic[i] = 1
				N //= i
		if N > 2:
			dic[N] = 1
		for i in dic.keys():
			lis.append(i)
		lis.sort()
		return lis


class Solution:

	def AllPrimeFactors(self, n):
		res = set()
		c = 2
		while n != 1:
			if n % c == 0:
				res.add(c)
				n = n // c
			else:
				c += 1
		return sorted(list(res))


import math as m

class Solution:

	def AllPrimeFactors(self, n):

		def prime(n):
			if n <= 1:
				return False
			sq = int(m.sqrt(n)) + 1
			for i in range(2, sq):
				if n % i == 0:
					return False
			return True
		a = []
		if n % 2 == 0:
			a += [2]
		for i in range(3, n + 1, 2):
			if n % i == 0 and prime(i) == True:
				a += [i]
		return a


class Solution:

	def AllPrimeFactors(self, N):
		factors = []
		i = 2
		while i * i <= N:
			if N % i == 0:
				factors.append(i)
				while N % i == 0:
					N //= i
			i += 1
		if N > 1:
			factors.append(N)
		return factors


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 AllPrimeFactors(self, N):
		lst = []
		if is_prime(N) == True:
			lst.append(N)
			return lst
		import math
		s = int(math.sqrt(N))
		for i in range(2, N):
			if N % i == 0 and is_prime(i) == True:
				lst.append(i)
		return lst


import math

class Solution:

	def AllPrimeFactors(self, N):

		def prime(c):
			if c < 2:
				return False
			for i in range(2, int(math.sqrt(c)) + 1):
				if c % i == 0:
					return False
			return True
		l = []
		ans = []
		for i in range(2, N // 2 + 1):
			if N % i == 0:
				l.append(i)
			else:
				continue
		l.append(N)
		for i in l:
			if prime(i):
				ans.append(i)
		return ans


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 AllPrimeFactors(self, N):
		l = []
		for i in range(1, N // 2 + 1):
			if N % i == 0 and isprime(i):
				l.append(i)
		if isprime(N):
			l.append(N)
		return l


import math

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

class Solution:

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


import math

class Solution:

	def AllPrimeFactors(self, N):
		primes = []
		if N % 2 == 0:
			primes.append(2)
		for i in range(3, N + 1, 2):
			if N % i == 0:
				if is_prime(i):
					primes.append(i)
		return primes

def is_prime(num):
	sq = int(math.sqrt(num))
	for i in range(3, sq + 1, 2):
		if num % i == 0:
			return False
	else:
		return True


X = int(1000000.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 AllPrimeFactors(self, N):
		pf = []
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0 and i:
				if primes[i] and i not in pf:
					pf.append(i)
				if primes[N // i] and N // i not in pf:
					pf.append(N // i)
		return pf


import math

class Solution:

	def AllPrimeFactors(self, N):

		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
		l = []
		if prime(N) == 0:
			l.append(N)
		else:
			for i in range(2, int(math.sqrt(N)) + 1):
				if N % i == 0:
					if prime(i) == 0:
						if i not in l:
							l.append(i)
					if prime(N // i) == 0:
						if N // i not in l:
							l.append(N // i)
		return 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 AllPrimeFactors(self, N):
		result = []
		for i in range(1, int(math.sqrt(N)) + 1):
			if N % i == 0:
				if Solution.checkPrime(i):
					result.append(i)
				if Solution.checkPrime(N // i) and i * i != N:
					result.append(N // i)
		return result


class Solution:

	def AllPrimeFactors(self, N):
		l = []
		p = 2
		while N != 1:
			if N % p == 0:
				l.append(p)
				N //= p
			else:
				p = p + 1
		l = sorted(list(set(l)))
		return l


class Solution:

	def AllPrimeFactors(self, N):
		i = 2
		ans = set()
		while i * i <= N:
			while N % i == 0:
				ans.add(int(i))
				N /= i
			i += 1
		if N > 1:
			ans.add(int(N))
		return sorted(list(ans))


class Solution:

	def AllPrimeFactors(self, N):
		if N <= 1:
			return []
		ans = []
		i = 2
		while i <= N:
			if N % i == 0:
				ans.append(i)
				N //= i
			else:
				i += 1
		return sorted(list(set(ans)))


import math

class Solution:

	def AllPrimeFactors(self, n):
		i = 2
		s = set()
		while i * i <= n:
			flag = 0
			while n % i == 0:
				n = n // i
				flag = 1
			if flag:
				s.add(i)
			i += 1
		if n > 1:
			s.add(n)
		return sorted(s)


class Solution:

	def AllPrimeFactors(self, N):

		def isPrime(n):
			if n < 4:
				return True
			if not n % 2 or not n % 3:
				return False
			i = 5
			while i * i <= n:
				if not n % i:
					return False
				i += (i + 3) % 6
			return True

		def nextPrime(n):
			if n < 5:
				return 2 * n - 1
			n += (n + 3) % 6
			while not isPrime(n):
				n += (n + 3) % 6
			return n
		a = []
		if N == 1:
			return a
		if isPrime(N):
			a.append(N)
			return a
		i = 2
		while True:
			f = True
			while not N % i:
				if f:
					a.append(i)
					f = False
				N //= i
				if isPrime(N):
					if N not in a:
						a.append(N)
					return a
				if N == 1:
					return a
			i = nextPrime(i)
		return a


import math

class Solution:

	def AllPrimeFactors(self, n):
		hs_set = set()
		ans = []
		for i in range(2, int(math.sqrt(n) + 1)):
			while n % i == 0:
				if i not in hs_set:
					ans.append(i)
					hs_set.add(i)
				n = n // i
		if n > 1:
			ans.append(n)
		return ans


class Solution:

	def AllPrimeFactors(self, N):
		import math
		a = []
		for i in range(2, int(math.sqrt(N)) + 1):
			if N % i == 0:
				a.append(i)
				while N % i == 0:
					N = N // i
		if N != 1:
			a.append(N)
		return a


import math

class Solution:

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

	def AllPrimeFactors(self, N):
		if self.isprime(N):
			return [N]
		ans = []
		lim = int(math.sqrt(N)) + 1
		for i in range(1, lim):
			if N % i == 0:
				ans.append(i)
				ans.append(N // i)
		sol = []
		for i in ans:
			if self.isprime(i):
				sol.append(i)
		return sorted(list(set(sol)))


class Solution:

	def AllPrimeFactors(self, N):
		a = set()
		while N % 2 == 0:
			a.add(2)
			N //= 2
		i = 3
		while i <= N ** 0.5:
			if N % i == 0:
				a.add(i)
				N //= i
			else:
				i += 2
		if N > 2:
			a.add(N)
		return sorted(list(a))


class Solution:

	def AllPrimeFactors(self, N):
		lis = []
		if N == 2:
			return [2]
		if N == 3:
			return [3]
		for i in range(2, int(N ** 0.5) + 1):
			while N % i == 0:
				lis.append(i)
				N //= i
		if N > 1:
			lis.append(N)
		s = set(lis)
		lis1 = list(s)
		lis1.sort()
		return lis1


import math

class Solution:

	def AllPrimeFactors(self, N):
		output = []
		for i in range(2, int(math.sqrt(N)) + 1):
			while N % i == 0:
				N = N // i
				if len(output) == 0 or output[-1] != i:
					output.append(i)
		if N != 1:
			output.append(N)
		return output


import math

class Solution:

	def AllPrimeFactors(self, N):
		factors = []
		temp = N
		k = int(math.sqrt(N))
		for i in range(2, k + 1):
			if temp % i == 0:
				factors.append(i)
			while temp % i == 0:
				temp = temp // i
		if temp != 1:
			factors.append(temp)
		return factors


import math

class Solution:

	def AllPrimeFactors(self, N):
		l = set()
		while N % 2 == 0:
			l.add(2)
			N = N / 2
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			while N % i == 0:
				l.add(i)
				N = N / i
		if N > 2:
			l.add(int(N))
		return sorted(l)


class Solution:

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

	def AllPrimeFactors(self, N):
		if N <= 1:
			return []
		elif self.isPrime(N):
			return [N]
		ans = []
		for i in range(2, N // 2 + 1):
			if N % i == 0 and self.isPrime(i):
				ans.append(i)
		return ans


class Solution:

	def AllPrimeFactors(self, n):

		def isPrime(n, r=False):
			if n < 4:
				return n > 1
			(isDivisible, k, i) = (lambda n, i, r: n if n % i else i if r else r, int(n ** 0.5), 2)
			while i <= k:
				d = isDivisible(n, i, r)
				if d - n:
					return d
				i += i - 1 if i in (2, 3) else (i - 3) % 6
			return True
		p = isPrime(n, True)
		(s, k) = ([], n)
		while k > 1:
			pk = isPrime(k, True) if n - k else p
			i = k if pk == True else pk
			c = 0
			while k % i == 0:
				k //= i
				c += 1
			s.append(i)
		return s


class Solution:

	def AllPrimeFactors(self, N):

		def isPrime(n):
			if n == 1:
				return False
			else:
				lim = int(n ** 0.5) + 1
				for i in range(2, lim):
					if n % i == 0:
						return False
				return True
		if N == 1:
			return []
		else:
			(lim, res) = (int(N ** 0.5) + 1, [])
			for i in range(1, lim):
				if N % i == 0:
					t = N // i
					if i == t and isPrime(i):
						res.append(i)
					else:
						if isPrime(i):
							res.append(i)
						if isPrime(t):
							res.append(t)
			return res


class Solution:

	def AllPrimeFactors(self, N):
		l = []
		if N < 2:
			return l
		if N % 2 == 0:
			l.append(2)
			while N % 2 == 0:
				N = N // 2
		if N % 3 == 0:
			l.append(3)
			while N % 3 == 0:
				N = N // 3
		i = 5
		while i <= N:
			if N % i == 0:
				l.append(i)
				while N % i == 0:
					N = N // i
			if N % (i + 2) == 0:
				l.append(i + 2)
				while N % (i + 2) == 0:
					N = N // (i + 2)
			i += 6
		return l


class Solution:

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


class Solution:

	def AllPrimeFactors(self, N):
		c = 2
		res = []
		while N > 1:
			if N % c == 0:
				res.append(c)
				N = N / c
			else:
				c = c + 1
		return sorted(list(set(res)))


class Solution:

	def AllPrimeFactors(self, N):
		i = 2
		l = []
		while i <= N:
			while N % i == 0:
				l.append(i)
				N = N // i
			i += 1
		l = set(l)
		l = list(l)
		l.sort()
		return l


import math

class Solution:

	def AllPrimeFactors(self, n):
		res = []
		if n == 1:
			return res
		if n % 2 == 0:
			res.append(2)
			while n % 2 == 0:
				n //= 2
		i = 3
		while i * i <= n:
			if n % i == 0:
				res.append(i)
				while n % i == 0:
					n //= i
			i += 2
		if n > 2:
			res.append(n)
		return res if len(res) != 0 else [n]


import math

class Solution:

	def AllPrimeFactors(self, n):
		res = []
		if n == 1:
			return res
		if n % 2 == 0:
			res.append(2)
			while n % 2 == 0:
				n = n // 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				res.append(i)
				while n % i == 0:
					n = n // i
		if n > 2:
			res.append(n)
		return res if len(res) != 0 else [n]


class Solution:

	def AllPrimeFactors(self, n):
		res = []
		if n == 1:
			return res
		if n % 2 == 0:
			res.append(2)
			n = self.factorise(n, 2)
		if n % 3 == 0:
			res.append(3)
			n = self.factorise(n, 3)
		i = 5
		while n > 1:
			if n % i == 0:
				res.append(i)
				n = self.factorise(n, i)
			i += 2
		return res if len(res) != 0 else [n]

	def factorise(self, n, i):
		while n % i == 0:
			n //= i
		return n


class Solution:

	def AllPrimeFactors(self, n):
		res = []
		if n == 1:
			return res
		if n % 2 == 0:
			res.append(2)
		if n % 3 == 0:
			res.append(3)
		i = 5
		while i <= n:
			if n % i == 0 and self.isPrime(i):
				res.append(i)
			if n % (i + 2) == 0 and self.isPrime(i + 2):
				res.append(i + 2)
			i += 6
		return res if len(res) != 0 else [n]

	def isPrime(self, n):
		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


class Solution:

	def AllPrimeFactors(self, N):
		no = 2
		dividend = N
		prime = []
		while dividend != 1:
			if dividend % no == 0:
				prime.append(no)
				while dividend % no == 0:
					dividend /= no
			no += 1
		return prime


class Solution:

	def AllPrimeFactors(self, N):
		i = 2
		v = set()
		while N > 1:
			if N % i == 0:
				N //= i
				v.add(i)
			else:
				i += 1
		ans = list(v)
		ans.sort()
		return ans


import math

class Solution:

	def AllPrimeFactors(self, N):
		res = []
		while N % 2 == 0:
			if 2 not in res:
				res.append(2)
			N = N // 2
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			while N % i == 0:
				if i not in res:
					res.append(i)
				N = N // i
		if N > 2 and N not in res:
			res.append(N)
		return res


class Solution:

	def AllPrimeFactors(self, N):
		divisor = 2
		factors = []
		while divisor <= N:
			if N % divisor == 0:
				factors.append(divisor)
				N = int(N / divisor)
			else:
				divisor += 1
		return sorted(list(set(factors)))


class Solution:

	def AllPrimeFactors(self, N):

		def prime(n):
			if n <= 1:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		l = []
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				if N // i != i:
					if prime(i):
						l.append(i)
					if prime(N // i):
						l.append(N // i)
				elif prime(i):
					l.append(i)
		if prime(N):
			l.append(N)
		l.sort()
		return l


class Solution:

	def AllPrimeFactors(self, N):
		res = []
		div = 2
		while N > 1:
			if N % div == 0:
				res.append(div)
				while N % div == 0:
					N //= div
			div += 1
		return res


import math

class Solution:

	def AllPrimeFactors(self, n):
		ans = []

		def prime(n):
			i = 1
			count = 0
			while i <= math.sqrt(n):
				if n % i == 0:
					count += 1
					if n // i != i:
						count += 1
				i += 1
			if count == 2:
				return True
			return False
		i = 1
		while i <= math.sqrt(n):
			if n % i == 0:
				if n // i == i:
					if prime(i):
						ans.append(i)
				else:
					if prime(i):
						ans.append(i)
					if prime(n // i):
						ans.append(n // i)
			i += 1
		return sorted(ans)


class Solution:

	def AllPrimeFactors(self, N):
		res = set()
		for i in range(2, N + 1):
			while N % i == 0:
				res.add(i)
				N //= i
		res = list(res)
		res.sort()
		return res