C LANGUAGE TECHNOLOGY

【C言語】約数の判定【約数の個数と和の計算】

悩んでいる人

C言語で約数の判定方法を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

約数の判定

約数とは,ある整数nに対してnを割り切る整数またはそれらの集合のことです.

約数の定義は,「整数a ≠ 0がnの約数である場合,ある整数bをとるとn = abが成立すること」です.

約数において整数は自然数の場合に限定して考えることが多いので,本記事でも自然数の約数について解説します.

つまり,n,a,bは自然数とします.

それでは,約数の判定方法を紹介していきます.

\(\mathcal{O}(n)\)の約数判定アルゴリズム

\(\mathcal{O}(n)\)の約数判定アルゴリズムでは,1~nの整数に対して順番に約数を判定します.

このアルゴリズムは\(\mathcal{O}(n)\)の計算量になります.

\(\mathcal{O}(n)\)の約数判定アルゴリズムのコードは以下になります.

実行結果は以下になります.

3行目の行末で100を入力したら,約数判定と約数の個数と和が正常に計算できていることがわかります.

\(\mathcal{O}(\sqrt{n})\)の約数判定アルゴリズム

\(\mathcal{O}(\sqrt{n})\)の約数判定アルゴリズムでは,1~\(\sqrt{n}\)の整数に対して順番に約数を判定し,整数iが約数ならばn/iも約数であるという性質を利用して約数の値を配列に保存します.

例えば,2は100の約数なので,100/2=50も100の約数になります.

このアルゴリズムの注意点として,約数の順番が昇順にならないことに注意して下さい.

もし昇順に並べるためにqsort関数でクイックソートする場合,\(\mathcal{O}(n \log n)\)の計算量がかかります.

\(\mathcal{O}(\sqrt{n})\)の約数判定アルゴリズムのコードは以下になります.

47行目のqsort関数でクイックソートして約数の順番を昇順に並べています.

実行結果は以下になります.

4行目でソート前,5行目でソート後の約数を表示しています.

まとめ

C言語で約数の判定方法を紹介しました.

約数の判定は基本的なアルゴリズムですので,きちんと習得しておきましょう!

最大公約数の計算方法を知りたいあなたはこちらからどうぞ.

C言語 ユークリッドの互除法
【C言語】ユークリッドの互除法で最大公約数と最小公倍数の計算

こういった悩みにお答えします. こういった私から学べます. 目次1 ユークリッドの互除法2 C言語のユークリッドの互除法で最大公約数と最小公倍数の計算3 拡張ユークリッドの互除法4 拡張ユークリッドの ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , ,