ある数numberがあったときにnumberの最大の素因数を求めるプログラムを書きたいです。自分で書いたコードは以下のコードです。
c
1#include <stdio.h> 2 3int main(void){ 4 int number=20; 5 int prime_factor=2; 6 while(1){ 7 while(number%prime_factor==0){ 8 number/=prime_factor; 9 } 10 prime_factor++; 11 if(number==1) break; 12 } 13 printf("%d\n", prime_factor); 14 return 0; 15}
考え方としては素数prime_factorを2からはじめ、numberがprime_factorで割り切れる間はnumberをどんどんprime_factorで割っていき、割り切れなくなったらprime_factorを1増やして同じことを繰り返す。この流れでnumberはどんどん小さくなっていき、最終的にnumber/prime_factorが1になったらその時に割ったprime_factorが最大の素数であるからその値を出力します。
上の場合number=20なのでprime_factorとして5が返ってくるはずなのですが6と出力され正しい値が得られません。このコードのどこが間違っているのでしょうか?また、もっといいアルゴリズムがあれば教えてほしいです。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。