tar0_puzzle の回答履歴

正整数Nの最大の素因数を求めるアルゴリズムがわかりません。 ネットで検索して一応出てきたのですが、どうしても理解できません。 int i,no=N; //Nは正整数 for(i=2;i*i<=no;i++){ while(no%i==0) no/=i; } iまたはnoのどちらかに求めたい素因数が入っています。 なぜこれで求めることができるのでしょうか？ noやiが非素数ということもあり得るのでは？ ずっと考えましたがわかりません。 誰か教えてください。

正整数Nの最大の素因数を求めるアルゴリズムがわかりません。 ネットで検索して一応出てきたのですが、どうしても理解できません。 int i,no=N; //Nは正整数 for(i=2;i*i<=no;i++){ while(no%i==0) no/=i; } iまたはnoのどちらかに求めたい素因数が入っています。 なぜこれで求めることができるのでしょうか？ noやiが非素数ということもあり得るのでは？ ずっと考えましたがわかりません。 誰か教えてください。