Иあっキー#ジャロさんが最初に作ったプログラムは共通の素数で順番に割っていくものなので大きな素数を指定した場合にはすごく時間がかかってしまいます。 Nが素数かどうかはN回ループして調べる必要はなくSQR(N)回で済むので「アルゴリズムは同一のままであっても高速化はできる」という例を書かせていただきました。 互除法を使用するのはそれよりも良い方法ですね。