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].

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def minSteps(self, n):
         """
         :type n: int
         :rtype: int
         """
         primeFactors=[]
         for i in range(2,int(n**.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
         
         """
         :type n: int
         :rtype: int
         """


class Solution:
     def minSteps(self, n):
         """
         :type n: int
         :rtype: int
         """
         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):
         """
         :type n: int
         :rtype: int
         """
         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):
         """
         :type n: int
         :rtype: int
         """
         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):
         """
         :type n: int
         :rtype: int
         """
         
         if n == 1:
             return 0
         
         # just manually does the first factor
         # useless step
         
         #lf = min(self.primes(n))
         
         #steps = lf
         #divs = n // lf
         
         
         return self.calcsteps(0, n) 
         # return self.calcsteps(steps, lf)   
         
         '''
         # this cleaner version of my approach starts at the lowest factor, then moves up when the number can no longer be cleanly divided
         # d stands for divisor (?)
         # both solutions run at 40ms
         
         ans = 0
         d = 2
         while n > 1:
             while n % d == 0:
                 ans += d
                 n /= d
             d += 1
         return ans
         '''
     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):
         # gets all prime factors of 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)
         # if a factor is three, you have to copy n, then paste it twice. 1 + 2 = 3, 1 + n - 1 = n
         # therefore, the number of steps is the sum of the primes
         
         return steps + sum(primes)


class Solution:
     def minSteps(self, n):
         """
         :type n: int
         :rtype: int
         """
         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
         
         
         """
         :type n: int
         :rtype: int
         """

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):
         """
         :type n: int
         :rtype: int
         """
         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)