Find the sum of all the numbers between the range l and r. Here each number is represented by the sum of its distinct prime factors. 
Note: For example, 6 is represented by 5 because 6 has two prime factors 2 and 3 and 2 + 3 = 5.
Example 1:
Input: l = 1, r = 2
Output: 2
Explanation: 1->0, 2->2 and 0+2=2.
1 has no prime factors.
Example 2:
Input: l = 1, r = 6
Output: 17
Explanation: 1->0, 2->2, 3->3, 4->2
5->5, 6->2+3=5, 0+2+3+2+5+5 = 17. 
Your Task:  
You dont need to read input or print anything. Complete the function sumOfAll() which takes l and r as input parameter and returns sum all the numbers ( as represented ) in the given range both L and R included.
Expected Time Complexity: O(nloglogn)
Expected Auxiliary Space: O(n)
Constraints:
1 <= l <= r <=10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:

	def sumOfAll(self, l, r):

		# code here



Solutions:
class Solution:
	ans = 0

	def sumOfAll(self, l, r):
		sum1 = 0
		ans = 0
		for i in range(l, r + 1):
			n = i
			factors = []
			d = 2
			while d * d <= n:
				while n % d == 0:
					factors.append(d)
					n //= d
				d += 1
			if n > 1:
				factors.append(n)
			self.ans += sum([*set(factors)])
		return self.ans


import math

def primefactorial(n):
	arr = []
	if n % 2 == 0:
		arr.append(2)
		while n % 2 == 0:
			n /= 2
	i = 3
	while math.sqrt(n) >= i:
		if n % i == 0:
			arr.append(i)
			while n % i == 0:
				n /= i
		i += 2
	if n > 2:
		arr.append(int(n))
	return arr

class Solution:

	def sumOfAll(self, l, r):
		s = 0
		if l == 1:
			l += 1
		for i in range(l, r + 1):
			if i < 4:
				s += i
			else:
				x = primefactorial(i)
				s += sum(x)
		return s


query = [0] * 10001
flag = False

def pre():
	query[1] = 0
	for i in range(2, 10001):
		if query[i] == 0:
			for j in range(2 * i, 10001, i):
				query[j] += i
	query[2] = 2
	for i in range(3, 10001, 2):
		if query[i] == 0:
			query[i] = i
	for i in range(2, 10001):
		query[i] += query[i - 1]

class Solution:

	def sumOfAll(self, l, r):
		global flag
		if not flag:
			pre()
			flag = True
		return query[r] - query[l - 1]


SPF = [i for i in range(10001)]
pre = [0] * 10002
for i in range(4, 10001, 2):
	SPF[i] = 2
for i in range(3, 10001, 2):
	if SPF[i] == i:
		for j in range(i * i, 10001, i):
			if SPF[j] == j:
				SPF[j] = i
for i in range(2, 10001):
	pre[i] += pre[i - 1]
	x = i
	while x != 1:
		z = SPF[x]
		pre[i] += z
		while SPF[x] == z:
			x //= SPF[x]

class Solution:

	def sumOfAll(self, l, r):
		return pre[r] - pre[l - 1]


import math

class Solution:

	def sumOfAll(self, l, r):
		return int(sum([sum(self.prime_factors(n)) for n in range(l, r + 1)]))

	def prime_factors(self, n):
		factors = {0}
		while n % 2 == 0:
			factors.add(2)
			n = n / 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				factors.add(int(i))
				n = n / i
		if n > 2:
			factors.add(int(n))
		return factors


import math

class Solution:

	def sumOfAll(self, le, r):
		li = []
		l = []
		for i in range(le, r + 1):
			if i == 1:
				l.append(i)
			while i % 2 == 0:
				l.append(2)
				i = i / 2
			for j in range(3, int(math.sqrt(i)) + 1, 2):
				while i % j == 0:
					l.append(j)
					i = i / j
			if i > 2:
				l.append(i)
			l = set(l)
			l = list(l)
			s = sum(l)
			li.append(s)
			l = []
		res = int(sum(li))
		return res


class Solution:

	def sumOfAll(self, L, R):

		def primeSum(prime, N):
			prime[1] = 1
			for i in range(2, N + 1):
				if prime[i] == 0:
					for j in range(i, N + 1, i):
						prime[j] += i
		primes = [0] * (R + 1)
		primeSum(primes, R)
		res = 0
		for i in range(L, R + 1):
			res += primes[i]
		return res


import math

class Solution:

	def sumOfAll(self, l, r):

		def primeFactors(n):
			Ans = []
			if n == 1:
				return 1
			while n % 2 == 0:
				Ans.append(2)
				n = n / 2
			for i in range(3, int(math.sqrt(n)) + 1, 2):
				while n % i == 0:
					Ans.append(int(i))
					n = n / i
			if n > 2:
				Ans.append(n)
			Ans = set(Ans)
			Ans = list(Ans)
			fin = 0
			for i in Ans:
				fin += i
			return fin
		Ts = 0
		for i in range(l, r + 1):
			Ts += primeFactors(i)
		return int(Ts)


class Solution:

	def sumOfAll(self, l, r):
		arr = [0] * (r + 1)
		arr[1] = 1
		prime = [0] * (r + 1)
		for i in range(2, r + 1):
			if prime[i] != 0:
				continue
			temp = i
			mul = 2
			while temp <= r:
				prime[temp] += 1
				arr[temp] += i
				temp = i * mul
				mul += 1
		return sum(arr[l:])


import math

class Solution:

	def sumOfAll(self, l, r):
		list_range = []
		list_prime = []
		for i in range(l, r + 1):
			if i == 1:
				list_prime.append(i)
			while i % 2 == 0:
				list_prime.append(2)
				i = i / 2
			for j in range(3, int(math.sqrt(i)) + 1, 2):
				while i % j == 0:
					list_prime.append(j)
					i = i / j
			if i > 2:
				list_prime.append(i)
			list_prime = set(list_prime)
			list_prime = list(list_prime)
			summ = sum(list_prime)
			list_range.append(summ)
			list_prime = []
		res = int(sum(list_range))
		return res


class Solution:

	def sumOfAll(self, l, r):
		all_sum = 0
		prime_set = set()
		prime_lsit = []
		sum_dict = {}
		for i in range(2, l):
			i_divs = set()
			i_sum = 0
			for k in prime_set:
				if i % k == 0:
					i_divs.add(k)
					i_sum += k
					if i / k in sum_dict:
						i_divs = i_divs | sum_dict[i / k]
						i_sum = sum(i_divs)
						break
			if len(i_divs) == 0:
				prime_set.add(i)
				i_sum += i
				i_divs = {i}
			sum_dict[i] = i_divs
		for i in range(l, r + 1):
			if i == 1:
				all_sum += 1
				continue
			i_sum = 0
			i_divs = set()
			for k in prime_set:
				if i % k == 0:
					i_divs.add(k)
					i_sum += k
					if i / k in sum_dict:
						i_divs = i_divs | sum_dict[i / k]
						i_sum = sum(i_divs)
						break
			if len(i_divs) == 0:
				prime_set.add(i)
				i_sum += i
				i_divs = {i}
			sum_dict[i] = i_divs
			all_sum += i_sum
		return all_sum


import math

class Solution:

	def sumOfAll(self, l, r):
		ans = 0
		for i in range(l, r + 1):
			temp = set()
			if i == 1:
				ans += 1
				continue
			while i % 2 == 0:
				temp.add(2)
				i = i // 2
			for j in range(3, int(math.sqrt(i)) + 1, 2):
				while i % j == 0:
					temp.add(j)
					i = i // j
			if i > 2:
				temp.add(i)
			ans += sum(temp)
		return ans


class Solution:

	def sumOfAll(self, l, r):
		arr = [0] * (r + 1)
		arr[1] = 1
		for i in range(2, r + 1):
			if arr[i] != 0:
				continue
			for j in range(i, r + 1, i):
				if j % i == 0:
					arr[j] += i
		count = 0
		for i in range(l, r + 1):
			count += arr[i]
		return count


class Solution:

	def sumOfAll(self, l, r):
		arr = [0] * (r + 1)
		arr[1] = 1
		for i in range(2, r + 1):
			if arr[i] > 0:
				continue
			arr[i] = i
			for j in range(2, r + 1):
				primeMultipleIdx = i * j
				if primeMultipleIdx > r:
					break
				arr[primeMultipleIdx] = arr[primeMultipleIdx] + i
		ans = 0
		for i in range(l, r + 1):
			ans += arr[i]
		return ans


import numpy as np

class Solution:

	def sumOfAll(self, l, r):

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

		def nr_multiples(p, a, b):
			count = 0
			q = a // p
			if q * p == a:
				count += 1
			q += 1
			while q * p <= b:
				count += 1
				q += 1
			return count
		res = 0
		for p in range(1, r + 1):
			if isprime(p):
				res += p * nr_multiples(p, l, r)
		if l == 1:
			res += 1
		return res


class Solution:

	def sumOfAll(self, l, r):
		p = [[True, 0] for i in range(r + 1)]
		p[1][1] = 1
		k = 2
		while k <= r:
			if p[k][0] == True:
				p[k][1] += k
				for i in range(2 * k, r + 1, k):
					p[i][0] = False
					p[i][1] += k
			k += 1
		ans = 0
		for i in range(l, r + 1):
			ans += p[i][1]
		return ans


import math

class Solution:

	def get_prime_factors(self, n):
		list = []
		sum = 0
		while n % 2 == 0:
			if 2 not in list:
				list.append(2)
			n = n / 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				if i not in list:
					list.append(i)
				n = n / i
		if n > 2 or (n == 1 and len(list) == 0):
			if n not in list:
				list.append(n)
		for x in list:
			sum += x
		return int(sum)

	def sumOfAll(self, l, r):
		sum = 0
		for i in range(l, r + 1):
			curr = self.get_prime_factors(i)
			sum += curr
		return sum


Primes = [0] * 10001

class Solution:

	def seive(self):
		Primes[1] = 1
		if Primes[2] == 2:
			return
		for i in range(2, 10001):
			if Primes[i] == 0:
				for j in range(i, 10001, i):
					Primes[j] = Primes[j] + i

	def sumOfAll(self, l, r):
		self.seive()
		s = 0
		for i in range(l, r + 1):
			s = s + Primes[i]
		return s


class Solution:

	def check_prime(self, i):
		lst = []
		p = i
		if i == 2 or i == 3:
			lst.append(i)
			return sum(lst)
		if i % 2 == 0 or i % 3 == 0:
			while i % 2 == 0:
				i = i // 2
				lst.append(2)
			while i % 3 == 0:
				i = i // 3
				lst.append(3)
			if i == 1:
				return sum(set(lst))
		for j in range(5, int(i ** 0.5) + 1, 6):
			while i % j == 0:
				i = i // j
				lst.append(j)
			while i % (j + 2) == 0:
				i = i // (j + 2)
				lst.append(j + 2)
			if i == 1:
				return sum(set(lst))
		lst.append(i)
		return sum(set(lst))

	def sumOfAll(self, l, r):
		sm = 0
		if l == 1:
			sm = 1
			l += 1
		for i in range(l, r + 1):
			sm += self.check_prime(i)
		return sm


class Solution:

	def sumOfAll(self, l, r):
		a = [True] * (r + 1)
		sum = 1 if l == 1 else 0
		for i in range(2, r + 1):
			if a[i]:
				if i >= l:
					sum = sum + i
				for j in range(2 * i, r + 1, i):
					a[j] = False
					if j >= l:
						sum = sum + i
		return sum


class Solution:

	def sumOfAll(self, l, r):
		seive = [0] * (r + 1)
		seive[1] = 1
		for i in range(2, r + 1):
			if seive[i] == 0:
				for j in range(i, r + 1, i):
					seive[j] += i
		return sum(seive[l:])


class Solution:

	def sumOfAll(self, l, r):
		ref = list()
		for i in range(r + 1):
			ref.append([])
		dp = [False] * (r + 1)
		for i in range(2, r + 1):
			if not dp[i]:
				for j in range(2 * i, r + 1, i):
					ref[j].append(i)
					dp[j] = True
		ans = int()
		for i in range(l, r + 1):
			for val in ref[i]:
				ans += val
			ans += i if dp[i] == False else 0
		return ans


class Solution:

	def sumOfAll(self, l, r):
		lst = [0] * (r + 1)
		lst[1] = 1
		for i in range(2, r + 1):
			if lst[i] != 0:
				continue
			for j in range(i, r + 1, i):
				if j % i == 0:
					lst[j] += i
		c = 0
		for i in range(l, r + 1):
			c += lst[i]
		return c


import math
primes = [0] * 10001

class Solution:

	def sieve(self):
		primes[1] = 1
		if primes[2] == 2:
			return
		for i in range(2, 10001):
			if primes[i] == 0:
				for j in range(i, 10001, i):
					primes[j] += i

	def sumOfAll(self, l, r):
		self.sieve()
		total_sum = 0
		for i in range(l, r + 1):
			total_sum += primes[i]
		return total_sum


class Solution:

	def sumOfAll(self, l, r):

		def prime(x):
			if x == 1:
				return 1
			sum = 0
			i = 2
			while i * i <= x:
				flag = 0
				while x % i == 0:
					flag = 1
					x //= i
				if flag == 1:
					sum += i
				i += 1
			if x > 1:
				sum += x
			return sum
		sum2 = 0
		while l <= r:
			sum2 = sum2 + prime(l)
			l = l + 1
		return sum2


import math

class Solution:

	def sumOfAll(self, l, r):
		s = 0
		spd = self.Sum(r)
		for i in range(l, r + 1):
			s += spd[i]
		return s

	def Sum(self, x):
		spd = [0] * (x + 1)
		spd[1] = 1
		for i in range(2, x + 1):
			if spd[i] == 0:
				for j in range(i, x + 1, i):
					spd[j] += i
		return spd


class Solution:

	def sumOfAll(self, l, r):
		msum = 0
		if l == 1:
			msum += 1
		primes = {k: 1 for k in range(2, r + 1)}
		for i in range(2, r + 1):
			if primes[i]:
				if i >= l:
					msum += i
				n = 2 * i
				while n <= r:
					if n >= l:
						msum += i
					primes[n] = 0
					n += i
		return msum


class Solution:

	def sumOfAll(self, l, r):
		prime = [True] * (r + 1)
		temp = [0] * (r + 2)
		temp[1] = 1
		temp[2] = 2
		for i in range(2, r + 1):
			if prime[i]:
				temp[i] = i
				j = 2 * i
				while j <= r:
					prime[j] = False
					temp[j] += i
					j += i
		ans = 0
		for i in range(l, r + 1):
			ans += temp[i]
		return ans


import math
l1 = []

class Solution:

	def sumOfAll(self, l, r):
		arr = [0] * (r + 1)
		arr[1] = 1
		for i in range(2, r + 1):
			if arr[i] != 0:
				continue
			for j in range(i, r + 1, i):
				if j % i == 0:
					arr[j] += i
		return sum(arr[l:r + 1])


class Solution:

	def __init__(self):
		self.primes = self.primes(r)

	def sumOfAll(self, l, r):
		numbers = []
		for i in range(l, r + 1):
			numbers += self.prime_factorization(i)
		return int(sum(numbers))

	def prime_factorization(self, n):
		numbers = []
		if n == 1:
			return [1]
		while n % 2 == 0:
			(numbers.append(2),)
			n = n / 2
		for i in range(3, int(n ** 0.5) + 1, 2):
			while n % i == 0:
				numbers.append(i)
				n = n / i
		if n > 2:
			numbers.append(n)
		return list(set(numbers))

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


def prime(n):
	l = [True for i in range(n + 1)]
	l[0] = l[1] = False
	for i in range(2, n):
		if l[i]:
			for j in range(i + i, n + 1, i):
				l[j] = False
	return l

class Solution:

	def sumOfAll(self, l, r):
		s = 0
		a = prime(r)
		p = []
		for i in range(len(a)):
			if a[i]:
				p.append(i)
		if l == 1:
			s += 1
			l += 1
		i = 0
		while i < len(p) and p[i] <= r:
			j = p[i]
			while j <= r:
				if j >= l and j <= r:
					s += p[i]
				j += p[i]
			i += 1
		return s


import math

def primes(n):
	d = [True] * (n + 1)
	d[0] = d[1] = False
	p = 2
	while p * p <= n:
		if d[p]:
			for i in range(p * p, n + 1, p):
				d[i] = False
		p += 1
	return d

def summ(primes, n):
	if n == 1:
		return 1
	s = 0
	sqt = int(math.sqrt(n))
	for i in range(2, sqt + 1):
		if not n % i:
			if i == int(n / i) and primes[i]:
				s += i
			else:
				if primes[i]:
					s += i
				if primes[int(n / i)]:
					s += int(n / i)
	return s

class Solution:

	def sumOfAll(self, l, r):
		prime = primes(r)
		res = 0
		for i in range(l, r + 1):
			if prime[i]:
				res += i
			else:
				res += summ(prime, i)
		return res


class Solution:

	def sumOfAll(self, l, r):
		cum = [0] * (r + 1)
		cum[1] = 1
		for i in range(2, r + 1):
			if cum[i]:
				continue
			for j in range(i, r + 1, i):
				if j % i == 0:
					cum[j] += i
		res = 0
		for i in range(l, r + 1):
			res += cum[i]
		return res


class Solution:

	def sumOfAll(self, l, r):
		b = [0] * (r + 1)
		b[1] = 1
		addit = 0
		for i in range(2, r + 1):
			if b[i] == 0:
				for j in range(i, r + 1, i):
					b[j] += i
		for i in range(l, r + 1):
			addit += b[i]
		return addit


n = 10001
prime = [1] * (n + 1)
p = 2
while p * p <= n:
	if prime[p] == 1:
		for i in range(p * p, n + 1, p):
			prime[i] = 0
	p += 1
p_set = set()
for i in range(2, n + 1):
	if prime[i] == 1:
		p_set.add(i)
p_s = sorted(p_set)

class Solution:

	def sumOfAll(self, l, r):
		ans = 0
		for i in range(l, r + 1):
			if i == 1:
				ans += 1
			elif i in p_set:
				ans += i
			else:
				t = i
				for j in p_s:
					if t % j == 0:
						ans += j
						while t % j == 0:
							t = t // j
						if t in p_set:
							ans += t
							break
						if t == 1:
							break
		return ans


class Solution:

	def sumOfAll(self, l, r):
		soln = 0
		prime = [True for i in range(r + 1)]
		p = 2
		while p * p <= r:
			if prime[p] == True:
				for j in range(p * p, r + 1, p):
					prime[j] = False
			p += 1
		for i in range(2, r + 1):
			if prime[i]:
				occur = r // i - (l - 1) // i
				soln += occur * i
		return soln + 1 if l == 1 else soln


def primeFactors(n):
	c = 2
	val = []
	while n > 1:
		if n % c == 0:
			val.append(c)
			n = n / c
		else:
			c = c + 1
	return set(val)

class Solution:

	def sumOfAll(self, l, r):
		arr = [0] * (r + 1)
		arr[1] = 1
		for i in range(2, r + 1):
			if arr[i] != 0:
				continue
			for j in range(i, r + 1, i):
				if j % i == 0:
					arr[j] += i
		count = 0
		for i in range(l, r + 1):
			count += arr[i]
		return count


class Solution:

	def sumOfAll(self, l, r):
		(primes, added) = ([True] * (r + 1), [0] * (r + 1))
		(primes[0], primes[1]) = (False, False)
		s = 0
		for i in range(2, r + 1):
			if primes[i]:
				for k in range(i, r + 1, i):
					primes[k] = False
					if k >= l:
						s += i
		if l == 1:
			s += 1
		return s


class Solution:

	def sumOfAll(self, l, r):
		sum_ = 0
		prime = [0] * (r + 1)
		prime[1] = 1
		for i in range(2, r + 1):
			if prime[i] == 0:
				prime[i] = i
				j = i + i
				while j <= r:
					prime[j] = prime[j] + i
					j += i
		for i in range(l, r + 1):
			sum_ += prime[i]
		return sum_


query = [0] * 10001
flag = False

def pre():
	query[1] = 1
	for i in range(2, 10001):
		if query[i] == 0:
			for j in range(2 * i, 10001, i):
				query[j] += i
	query[2] = 2
	for i in range(3, 10001, 2):
		if query[i] == 0:
			query[i] = i
	for i in range(2, 10001):
		query[i] += query[i - 1]

class Solution:

	def sumOfAll(self, l, r):
		global flag
		if not flag:
			pre()
			flag = True
		return query[r] - query[l - 1]

class Solution_bf:

	def __init__(self):
		self.primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]
		self.psize = len(self.primes)

	def GetFactors(self, num, fset):
		if num in self.primes:
			fset.add(num)
			return
		for j in range(self.psize):
			if self.primes[j] > num:
				break
			if num % self.primes[j] == 0:
				fset.add(self.primes[j])
				factor = num // self.primes[j]
				if factor in self.primes or factor == 1:
					fset.add(factor if factor != 1 else num)
					break
				else:
					self.GetFactors(factor, fset)

	def sumOfAll(self, l, r):
		asum = 0
		pairs = [[4, 13], [7, 10], [5, 9], [1, 11]]
		skip = False
		for p in pairs:
			if p[0] == l and p[1] == r:
				skip = True
				break
		if not skip:
			print('l=%d, r=%d' % (l, r))
		for i in range(l, r + 1):
			if i == 1 or i == 2 or i == 3:
				asum += i
			else:
				fset = set()
				self.GetFactors(i, fset)
				asum += sum(fset)
		return asum


import math

class Solution:

	def sumOfAll(self, l, r):

		def solve(n):
			if n == 1:
				return 1
			seti = set()
			i = 2
			p = math.ceil(math.sqrt(n))
			while n > 1 and i <= p:
				while n % i == 0:
					seti.add(i)
					n //= i
				i += 1
			if n > 1:
				seti.add(n)
			return sum(seti)
		ans = 0
		for i in range(l, r + 1):
			ans += solve(i)
		return ans