@prateekbhaisora
Great question and Great Explanation!
Here is my equivalent Python submission:
from typing import List
class Solution:
def sieve (self, n):
isPrime = [0] * (n+1)
for i in range(n+1):
isPrime[i] = i;
for i in range(2, n+1):
if (isPrime[i] == i):
for j in range(i*i, n+1, i):
if (isPrime[j] == j):
isPrime[j] = i # Calculating SPF using Sieve
return isPrime
def sumOfPowers(self, a : int, b : int) -> int:
ans = 0
spf = self.sieve(b)
for i in range(a, b+1):
num = i
powcnt = 0
while (num != 1):
powcnt += 1
num //= spf[num]
ans += powcnt
return ans
# TC = O(b.log(b)) SC = O(b.log(b))
@prakhargarg4166