Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step: 

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.




Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'. 


Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.




Note:

The n will be in the range [1, 1000].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Starter code: class Solution:
    def minSteps(self, n: int) -> int:
        

Solutions:
class Solution:

	def minSteps(self, n):
		primeFactors = []
		for i in range(2, int(n ** 0.5) + 1):
			while n % i == 0:
				primeFactors.append(i)
				n = n // i
		if n > 1:
			primeFactors.append(n)
		return sum(primeFactors)


class Solution:

	def minSteps(self, n):
		m = n
		sum = 0
		tmp = 2
		if m == 1:
			return 0
		if m == 2:
			return 2
		else:
			while m > tmp:
				k = m % tmp
				if k == 0:
					m = m / tmp
					sum += tmp
				else:
					tmp = tmp + 1
			sum = sum + tmp
			return sum


class Solution:

	def minSteps(self, n):

		def factors(n):
			d = 2
			while d * d <= n:
				while n % d == 0:
					n /= d
					yield d
				d += 1
			if n > 1:
				yield n
		return int(sum(factors(n)))


class Solution:

	def minSteps(self, n):
		primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
		ret = 0
		for p in primes:
			while not n % p:
				n /= p
				ret += p
		return int(ret + n * (n > 1))


class Solution:

	def minSteps(self, n):
		res = 0
		p = 2
		while n > 1:
			while n % p == 0:
				res += p
				n /= p
			p += 1
		return res


class Solution:

	def minSteps(self, n):
		if n == 1:
			return 0
		isPrime = [True for _ in range(n + 1)]
		isPrime[1] = False
		prime = []
		for i in range(2, n + 1):
			if isPrime[i] == True:
				prime.append(i)
				k = 1
				while (k + 1) * i <= n:
					isPrime[(k + 1) * i] = False
					k += 1
		if isPrime[n]:
			return n
		(cnt, i) = (0, 0)
		while n > 1:
			while n % prime[i] == 0:
				cnt += prime[i]
				n = n // prime[i]
			if isPrime[n]:
				return cnt + n
			i += 1
		return cnt


class Solution:

	def minSteps(self, n):
		if n == 1:
			return 0
		return self.calcsteps(0, 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
		w = 2
		while i * i <= n:
			if n % i == 0:
				return False
			i += w
			w = 6 - w
		return True

	def primes(self, n):
		primfac = []
		d = 2
		while d * d <= n:
			while n % d == 0:
				primfac.append(d)
				n //= d
			d += 1
		if n > 1:
			primfac.append(n)
		return primfac

	def calcsteps(self, steps, divs):
		if self.isprime(divs):
			return divs + steps
		primes = self.primes(divs)
		return steps + sum(primes)


class Solution:

	def minSteps(self, n):
		s = 0
		for d in range(2, n + 1):
			while n % d == 0:
				s += d
				n /= d
		return s


class Solution:

	def minSteps(self, n):
		d = 2
		ans = 0
		while n > 1:
			while n % d == 0:
				ans += d
				n = n / d
			d = d + 1
		return ans


class Solution(object):

	def minSteps(self, n):
		steps = 0
		div = 2
		while n > 1:
			if n % div == 0:
				steps += div
				n = n / div
			else:
				div += 1
		return steps


class Solution:

	def minSteps(self, n):
		f = 2
		s = 0
		while f * f <= n:
			while n % f == 0:
				s += f
				n = int(n / f)
			f += 1
		if n > 1:
			s += n
		return int(s)