約数列挙

任意の非負整数Nの約数を求めたい場合、愚直な実装をすると１からNまでの数字すべてがNの約数かどうかを確認することになると思います。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>ans;
  for (int i=1;i<=n;i++)if(n%i==0)ans.emplace_back(i);
  for (int i=0;i<ans.size();i++)cout << ans[i] << endl;
  return 0;
}

となると思います。

しかし、約数が見つかったときに、N//iも約数として列挙するようにすると、計算量√Nで約数をすべて列挙することができます。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>ans;
  set<int>irane;
  for (int i=1;i<=int(sqrt(n))+10;i++){
    if(n%i!=0)continue;
    if(irane.count(i)>0)continue;
    ans.emplace_back(i);
    ans.emplace_back(n/i);
    irane.insert(i);
    irane.insert(n/i);
  }
  sort(ans.begin(),ans.end());
  for (int i=0;i<ans.size();i++)cout << ans[i] << endl;
  return 0;
}

set使わない方が良かったな…（あとでカエル）