Prime factorization solution [C++]


  • 0
    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?


Log in to reply
 

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