約数全列挙 C++

お久しぶりです。Arkです。

最近はAtCorderの400点問題を主に解いており、その過程で必要になった知識を書いていこうと思います。今回の内容は約数全列挙です。

• 僕が解いた問題はこちら

https://atcoder.jp/contests/abc112/tasks/abc112_d

一応僕のソースコードも張っておきます。
https://atcoder.jp/contests/abc112/submissions/5828856
 

一目見て約数が必要だな～～～とわかる問題になっています。Mの制約が10^9と大きいので少し工夫が必要です。まぁ、少し考えてもいい解法が思い浮かばなかったのでネットで検索しました。

するとO(√M)解法がヒットしました。以下にソースコード張ります！

//nの約数を列挙
vector<long long> divisor(long long n)
{
	vector<long long> num;
	for(long long i=1;i*i<=n;++i){
		if(n%i==0){
			num.push_back(i);
			if(i*i!=n)
				num.push_back(n/i);
		}
	}
	return num;
}

これは何をしているかというと、例えばn=100としたとき、for文でiを1~10まで回します。
100をi (1~10)で割り切ることができるかを判定して（一つ目のif文の判定) 、割り切ることができたら n/iも約数であるのでこの二つを列挙します。しかし、i*i==nになってしまうと、今回の場合10を二回列挙してしまうことになるので例外処理 (二つ目のif文) をします。
約数列挙の部分が重複して記載することになりますが、例の挙げたn=100を列挙するソースコードは以下のようになります。

#include "bits/stdc++.h"
using namespace std;

//nの約数を列挙
vector<int> divisor(int n)
{
	vector<int> num;
	for(int i=1;i*i<=n;++i){
		if(n%i==0){
			num.push_back(i);
			if(i*i!=n)
				num.push_back(n/i);
		}
	}
	return num;
}

int main(){
	vector<int> v=divisor(100);
	for(int i=0;i<v.size();i++)cout<<v[i]<<",";
	return 0;
}

以上となります。求める約数の数によっては、intの部分をlong longなどに変更してお使いください。

次は素数の生成方法の記事を書きたいなと思っているのでもしよければ覗いてあげてください。僕がとても喜びます(^▽^)/