<p>There is only one character <code>&#39;A&#39;</code> on the screen of a notepad. You can perform one of two operations on this notepad for each step:</p>

<ul>
	<li>Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).</li>
	<li>Paste: You can paste the characters which are copied last time.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the minimum number of operations to get the character</em> <code>&#39;A&#39;</code> <em>exactly</em> <code>n</code> <em>times on the screen</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Initially, we have one character &#39;A&#39;.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get &#39;AA&#39;.
In step 3, we use Paste operation to get &#39;AAA&#39;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

from collections import defaultdict
import math
import numpy as np
class Solution:
    def __init__(self):
        pass
        #self.table=set([4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 21, 20, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 56, 55, 57, 58, 60, 63, 62, 64, 65, 66, 69,68, 70, 72, 75, 74, 76, 78, 77, 80])
        #self.table.union(set([4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 21, 20, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 56, 55, 57, 58, 60, 63, 62, 64, 65, 66, 69,68, 70, 72, 75, 74, 76, 78, 77, 80]*3))
        #print(self.table)
    
    def minSteps(self, n: int) -> int:
        if n==1:
            return 0
        #def primeFactors(n):
        #ret=defaultdict(int)
        ret=[]
        while n%2==0:
            #ret[2]+=1
            ret.append(2)
            n=n//2
        i=3
        while i<int(math.sqrt(n))+1:
            while n%i==0:
                #ret[i]+=1
                ret.append(i)
                n=n//i
            i=i+2
        
        '''for i in range(3,int(math.sqrt(n))+1,2):
            if i in self.table:
                continue
            while n%i==0:
                ret[i]+=1
                n=n//i'''
        
        if n>2:
            #ret[n]+=1
            ret.append(n)

        return sum(ret)
         

28306