abc180_c - Cream Puff
08 Jan 2021 — Tags: divisibility,factors,number_theory,implementation — URLGet factors up to $\sqrt{n}$ (with their co-factors) and print them.
Time complexity: $O(\sqrt{n} \log{\sqrt{n}})$
Memory complexity: $O(2 \sqrt{n})$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
ll n;
cin >> n;
set<ll> factors;
for (ll x = 1, sq = sqrt(n); x <= sq; ++x)
{
if (n % x == 0)
{
factors.insert(x);
factors.insert(n / x);
}
}
for (auto x : factors)
cout << x << endl;
return 0;
}