# Prime factorization solution [C++]

• Factorize the number into prime numbers. Suppose n = p1^m1 * p2^m2, then the number of steps is
p1m1 + p2m2.
That is the following steps:
1 Construct p1^m1:
1.1 Copy 1 and paste p1-1 times
1.2 Copy all and paste p1-1 times
...
1.m1 Copy all and paste p1-1 times

2 Construct n from p1^m1:
2.1 Copy all and paste p2-1 times
...
2.m2 Copy all and paste p2-1 times

``````class Solution {
public:
int minSteps(int n) {
map<int, int> count;
for (int i=2; i<=sqrt(n); i++) {
if (n%i == 0 && prime(i)) {
count[i] = 0;
while (n%i == 0) {count[i]++, n/=i;}
}
}
if (n>1) count[n] = 1;
return accumulate(count.begin(), count.end(), 0, [](int s, std::pair<int ,int> p) {
return s + p.first * p.second;
});
}

bool prime(int n) {
if (n==1) return false;
if (n==2) return true;
for (int i=2; i<sqrt(n); i++) {
if (n%i == 0) return false;
}
return true;
}
};
``````

I think the prime function can be improved?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.