最近約数を全部列挙するプログラムをjavaで書く方法を2通り思いついたのでそれを書いていきたいと思います。（今後自分が競プロとか参加した時にどこかで使う機会もありそうだなと思ったのでメモとしての役割もありますが）
そもそも約数って何？(一一")
数学において整数 N の約数とは、N を割り切る整数またはそれらの集合のことである。（wikipediaより）
約数って何？って聞かれたときにこう答えられたらかっこいいですね。僕は「6÷2って整数で割り切れるよね？じゃこの時2は6の約数なんよね」といったノリで答えてしまいそうな気がします。
プログラム的には、数字a,b(0 < aかつ0 < b <= a)があり、a%b == 0 になる時bはaの約数と言えますね。
これを頭に入れてとりあえず組んでいきます。
パターン1：とりあえず線形探索
import java.util.*;
public class Divisor {
public static void main(String[] args) {
System.out.println("数字を入力して下さい");
Scanner sc = new Scanner(System.in);
long N = sc.nextLong();
for(long i = 1; i <= N; i++){
if(N % i == 0 && i == N) System.out.print(i);
else if(N % i == 0) System.out.print(i + ",");
}
}
}
出力結果
①Nに123を入れた時
1,3,41,123
②Nに23456を入れた時
1,2,4,8,16,32,733,1466,2932,5864,11728,23456
③Nに6を入れた時
1,2,3,6
大丈夫そうですね。
でもこのプログラム、もっと改良できそうですね。
例えば28の約数を求める際に1が求まった際、同時に28も求まりそうですね。
同様に2が求まった際、14も求まりそうですね。
同様に4が求まったら7も求まりますね。
ということはこの時6まで求まればわざわざ7以降は調べる必要ないですね。
（ここまで求めた数字の中で求まった数字以外で自然数を掛け合わせて28にならないからです。）
64の約数を考えた時も8まで求めてしまえば9以降は調べる必要もなさそうです。
そうです。これ√Nまで求めてしまえばそれ以降調べなくてもいいのです。
ではこれをプログラムにしていきましょう。
パターン1：√Nまで求めるパターン
import java.util.*;
public class Divisor {
public static void main(String[] args) {
System.out.println("数字を入力して下さい");
Scanner sc = new Scanner(System.in);
long N = sc.nextLong();
double rootN = Math.sqrt(N);
long NN = (long)rootN;
ArrayList<Long> divisors = new ArrayList<>();
for(long i = 1; i <= NN; i++){
if(N % i == 0){
if(N/i != i){
divisors.add(i);
divisors.add(N/i);
}
else {
divisors.add(i);
}
}
}
Collections.sort(divisors); //ソート
String Ans = "";
for(Long num : divisors){
Ans += num + ",";
}
System.out.println(Ans.substring(0,Ans.length() - 1));//最後の","を省く
}
}
といった感じで√Nまで求めた場合でもプログラムが完成しました。
AtCoderのテストコードで試しにN = 100000000を計算させてみたところ
①の線形探索では
実行時間:2658 ms
②の改良版では
実行時間:264 ms
でした。なんと計算時間が10倍も違いますね。
まとめ
今回は約数を求めるという簡単な問題ですが、簡単な問題でもこういった数学的な工夫を凝らせるのはプログラムの実装の面白い所ですね。例えば1から100まで求める際もfor文を使っていちいち足す必要が無く、シグマ計算でn(n + 1)/2にn = 100を代入すれば計算量1で済みますもんね。
「できるだけ計算量を減らすにはどうしたらよいか」、そういった思考をこれからも続けていくためにも数学の勉強も頑張ろうと思いました。