公約数は最大公約数の約数であるので, まずは最大公約数を求める.

この約数からいくつか選んで互いに素にするためには, 最大公約数を素因数分解して各素因数だけをもつ約数を選ぶのが最適である. よって, 選べる最大の数は素因数の数 + 1 (1 も含めていい) である.