You are given a positive number N. Using the concept of Sieve, compute its prime factorisation.
Example:
Input: 
N = 12246
Output: 
2 3 13 157
Explanation: 
2*3*13*157 = 12246 = N.
Your Task:
Comple the function findPrimeFactors(), which takes a positive number N as input and returns a vector consisting of prime factors. You should implement Sieve algorithm to solve this problem.
 
Expected Time Complexity: O(Nlog(log(N)).
Expected Auxiliary Space: O(N).
Constraints:
1<=N<=2*10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def sieve(self):

        

    def findPrimeFactors(self, N):

        # Code here

Solutions:
class Solution:

	def sieve(self):
		ma = 200001
		self.prime = [1] * ma
		self.prime[0] = self.prime[1] = 0
		i = 2
		while i * i < ma:
			if self.prime[i]:
				for j in range(i * i, ma, i):
					self.prime[j] = 0
			i += 1

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


class Solution(object):

	def sieve(self):
		pass

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


import math

class Solution:

	def sieve(self):
		p = 2
		self.arr = [True] * 200001
		while p * p <= 200000:
			if self.arr[p] == True:
				for i in range(p * p, 200001, p):
					self.arr[i] = False
			p += 1

	def findPrimeFactors(self, N):
		if N == 1:
			return []
		ans = []
		while N > 1:
			if self.arr[N] == True:
				ans.append(N)
				break
			x = int(math.sqrt(N)) + 1
			for num in range(2, x):
				if self.arr[num] == True and N % num == 0:
					ans.append(num)
					N = N // num
					break
		return ans