Untitled

// returns prime factors & number of times it occurs as pairs
vector <pair <int, int> > PrimeFactor(int n) {
    vector <pair <int, int> > pf;
    int sz = primes.size();
    for (int i = 0; i < sz && primes[i] * primes[i] <= sq; i++) {
        int cnt = 0;
        if (n % primes[i] == 0) {
            while (n % primes[i] == 0) {
                cnt++;
                n /= primes[i];
            }
            if (cnt > 0) {
                pf.push_back(make_pair(primes[i], cnt));
            }
        }
    }
    if (n > 1) {
        pf.push_back(make_pair(n, 1));
    }
    
    return pf;
}