C言語で約数の判定方法を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
約数の判定
約数とは，ある整数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)\)の約数判定アルゴリズムのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> int main(void) { unsigned long i, n, sum, nr_divisors; printf("Please input a natural number: "); scanf("%lu", &n); sum = nr_divisors = 0; for (i = 1; i <= n; i++) { if (n % i == 0) { printf("%lu ", i); sum += i; nr_divisors++; } } printf("\nnr_divisors = %lu, sum = %lu\n", nr_divisors, sum); return 0; } |
実行結果は以下になります．
3行目の行末で100を入力したら，約数判定と約数の個数と和が正常に計算できていることがわかります．
|
1 2 3 4 5 |
$ gcc divisor.c $ a.out Please input a natural number: 100 1 2 4 5 10 20 25 50 100 nr_divisors = 9, sum = 217 |
\(\mathcal{O}(\sqrt{n})\)の約数判定アルゴリズム
\(\mathcal{O}(\sqrt{n})\)の約数判定アルゴリズムでは，1～\(\sqrt{n}\)の整数に対して順番に約数を判定し，整数iが約数ならばn/iも約数であるという性質を利用して約数の値を配列に保存します．
例えば，2は100の約数なので，100/2=50も100の約数になります．
このアルゴリズムの注意点として，約数の順番が昇順にならないことに注意して下さい．
実装で利用するsqrt関数を知りたいあなたはこちらからどうぞ．
また，qsort関数でクイックソートする場合，\(\mathcal{O}(n \log n)\)の平均計算量になります．
qsort関数の使い方を知りたいあなたはこちらからどうぞ．
\(\mathcal{O}(\sqrt{n})\)の約数判定アルゴリズムのコードは以下になります．
47行目のqsort関数でソートして約数の順番を昇順に並べています．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> int arraycmp(const void *p1, const void *p2) { return *(const unsigned long *) p1 > *(const unsigned long *) p2; } int main(void) { unsigned long i, n, sum, nr_divisors; unsigned long *array; printf("Please input a natural number: "); scanf("%lu", &n); if ((array = malloc(sizeof(unsigned long) * n)) == NULL) { fprintf(stderr, "Error: cannot allocate memory %zu bytes.\n", sizeof(unsigned long) * n); exit(1); } sum = nr_divisors = 0; for (i = 1; i * i <= n; i++) { if (n % i == 0) { sum += i; array[nr_divisors++] = i; if (i * i != n) { sum += n / i; array[nr_divisors++] = n / i; } } } for (i = 0; i < nr_divisors; i++) { printf("%lu ", array[i]); } printf("\n"); qsort(array, nr_divisors, sizeof(unsigned long), arraycmp); for (i = 0; i < nr_divisors; i++) { printf("%lu ", array[i]); } printf("\nnr_divisors = %lu, sum = %lu\n", nr_divisors, sum); free(array); return 0; } |
実行結果は以下になります．
4行目でソート前，5行目でソート後の約数を表示しています．
|
1 2 3 4 5 6 |
$ gcc divisor2.c $ a.out Please input a natural number: 100 1 100 2 50 4 25 5 20 10 1 2 4 5 10 20 25 50 100 nr_divisors = 9, sum = 217 |
まとめ
C言語で約数の判定方法を紹介しました．
約数の判定は基本的なアルゴリズムですので，きちんと習得しておきましょう！
最大公約数の計算方法を知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
