【競技プログラミング】long型にしてもエラーが起きる

Question

前提・実現したいこと

競技プログラミングatcoderのC問題(https://atcoder.jp/contests/abc144/tasks/abc144_c)の入力例で10000000019を入力するとlong型でコードを書いたつもりがループしてしまいます。どこが間違っているのでしょうか？

発生している問題・エラーメッセージ

cmdがフリーズ、atcoderのコードテストも何も出ませんでした。実行時間も超過してしまいました。

該当のソースコード

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		ArrayList<Long> a = new ArrayList<Long>();
		ArrayList<Long> b = new ArrayList<Long>();
		long t = 0;
		long g = 0;
		for (long i = 1;i < N;i++) {
			if (N%i == 0) {
				t = i;
				g = N/i;
				a.add(t);
				b.add(g);
			}
		}
		int c = 0;
		int i = 0;
		long S[] = new long[a.size()];
		while (c < a.size()) {
			S[i] = a.get(i)+b.get(i);
			i++;
			c++;
		}
		Arrays.sort(S);
		System.out.println((long)S[0]-2);
	}
}

試したこと

調べたところlong型を使用するときに数字の末尾にLを付けるとあったのですがスキャナーでは付けれませんでした。
BigIntegerも試しましたが、よくわかりませんでした。

補足情報（FW/ツールのバージョンなど）

Answer 1

単純に割り算に時間がかかります。
実験：Ideoneでの実行結果
単純に試し割りしていくだけでも5秒以上かかってしまいます。
割り算の回数を減らす工夫をする必要があります。
一般に整数nがabで表せるなら、baでも表せます。
この大小関係は√nを境に入れ替わるので、√n以下の整数で試し割りすればいいことになります。

Comments

[junpeihamasaki]

詳しい回答ありがとうございます
計算についての理解が浅かったので気を付けます。

[swordone]

なお、
> 調べたところlong型を使用するときに数字の末尾にLを付けるとあったのですが
これは整数リテラル(プログラム上に直接記述する数)の場合の話です。メソッドなどでその必要は無いです。

また、0<a<bでa*b=n(一定)の条件下では、a+bの値はaが√nに近いほど小さくなります。

Answer 2

単に遅すぎてダメというだけだと思います.