Identify Smith Numbers
Divisors
Divisors of a number are numbers , where and .
Depending on the requirement of the challenge, we have two good methods to calculate divisors.
When we have , and we have few numbers to calculate the divisors of, we can check every number from to , and if , we add and to our set of divisors.
set<int> arr;
for (int i = 1;i < sqrt(N) + 1; i++) {
if (N % i == 0) {
arr.insert(i);
arr.insert(N / i);
}
}
If and we have a lot of queries, we can build a sieve such that Ar[x] contains the divisors.
vector <vector <int> > divisors(1000001, vector<int> ());
for (int k = 1; k < 1000001; k++) {
for (int i = 1; i < 1000001/k; i++) {
divisors[i * k].push_back(k);
}
}
Now for each query Q
, divisors[Q]
contains all the divisors.
Related challenge for Divisors