Divisors -

Finding the divisors of an integer can be done in many ways. Simply looping over all the possible divisors of N gives an O(N) solution, which is far too slow. However notice we only need to loop up to sqrt(N) since each factor pair has exactly one factor <= sqrt(N) and another one >= sqrt(N), so each time we find something <= sqrt(N) we have actually also found another factor which is >= sqrt(N).

void divisors(int N){
set<int> divs;
for(int i = 1; i * i <= N; i++){
if(N % i == 0){
divs.insert(i);
divs.insert(N/i);
}
}
for(int u : divs){
cout << u << ‘\n’;
}
}

It is also possible to find the prime factorization of a number in O(sqrt(N)) time as shown:

void primeFact(int N){
map<int, int> factor;
for(int i = 2; i * i <= N; i++){
while(N % i == 0){
factor[i]++;
N /= i;
}
}
if(N > 1){
factor[N]++;
}
for(auto [fac, num] : factor){
cout << fac << ‘ ‘ << num << ‘\n’;
//fac^num
}
}