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社で自分に合うスクールを見つけましょう．後悔はさせません！
C言語で素数の判定方法を紹介します．
具体的には，エラトステネスの篩（ふるい），エラトステネスの篩を改良したサンダラムの篩とアトキンの篩を解説します．
目次
エラトステネスの篩（ふるい）
エラトステネスの篩（ふるい）は，古代ギリシアの科学者のエラトステネスにより提案された素数を判定するアルゴリズムです．
1からNまでの自然数の中で素数を判定する時によく利用されます．
N以下の整数の集合から合成数（2つ以上の素数の積で表現できる自然数）を次々と篩にかけることで，最終的に素数のみを残す（判定する）方法になります．
エラトステネスの篩は以下の動画がわかりやすいです．
C言語でエラトステネスの篩のコードは以下になります．
|
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 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <math.h> #define N 100 #define PRIME 1 #define NON_PRIME 0 int main(void) { size_t i, j; size_t prime[N]; size_t sqrt_num = sqrt(N); size_t prime_num = 0; prime[0] = NON_PRIME; for (i = 1; i < N; i++) { prime[i] = PRIME; } for (i = 1; i < sqrt_num; i++) { if (prime[i] == PRIME) { for (j = i + 1; (i + 1) * j <= N; j++) { prime[(i + 1) * j - 1] = NON_PRIME; } } } for (i = 0; i < N; i++) { if (prime[i] == PRIME) { printf("%zu ", i + 1); prime_num++; } } printf("\n"); printf("prime_num = %zu\n", prime_num); return 0; } |
実行結果は以下になります．
1から100までの素数を正しく判定できました．
|
1 2 3 4 |
$ gcc eratosthenes.c $ a.out 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 prime_num = 25 |
サンダラムの篩
サンダラムの篩は，1934年にサンダラムにより提案された素数を判定するアルゴリズムです．
エラトステネスの篩は自然数を篩にかけるのに対して，サンダラムの篩は奇数を篩にかけることが特徴です．
これにより，サンダラムの篩は約2倍の高速化が期待できます．
C言語でサンダラムの篩のコードは以下になります．
|
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 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #define N 100 #define PRIME 1 #define NON_PRIME 0 int main(void) { size_t i, j; size_t prime[N + 1]; size_t prime_num = 0; size_t n = N / 2; size_t prime_index = 0; for (i = 0; i < n; i++) { prime[i] = PRIME; } for (i = 1; i < n; i++) { for (j = i; j <= (n - i) / (2 * i + 1); j++) { prime[i + j + 2 * i * j] = NON_PRIME; } } if (N > 2) { prime[prime_index++] = 2; } for (i = 1; i < n; i++) { if (prime[i] != 0) { prime[prime_index++] = i * 2 + 1; } } for (i = 0; i <= N; i++) { if (prime[i] != 0) { printf("%zu ", prime[i]); prime_num++; } else { break; } } printf("\n"); printf("prime_num = %zu\n", prime_num); return 0; } |
実行結果は以下になります．同様です．
|
1 2 3 4 |
$ gcc sundaram.c $ a.out 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 prime_num = 25 |
アトキンの篩
アトキンの篩は，2003年にアトキンにより提案された素数を判定するアルゴリズムです．
アトキンの篩の特徴は，自然数を60で割った余りを返す処理があることです．
この処理より，アトキンの篩は他の篩より高速化することが可能になります．
C言語でアトキンの篩のコードは以下になります．
|
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <math.h> /* assume that N >= 5. */ #define N 100 #define PRIME 1 #define NON_PRIME 0 int main(void) { size_t sqrt_num = sqrt(N); size_t i, j, x, y, z; size_t prime[N + 1]; size_t prime_num = 3; for (i = 0; i < N; i++) { prime[i] = NON_PRIME; } for (x = 1; x <= sqrt_num; x++) { for (y = 1; y <= sqrt_num; y++) { z = 4 * x * x + y * y; if (z <= N && (z % 60 == 1 || z % 60 == 13 || z % 60 == 17 || z % 60 == 29 || z % 60 == 37 || z % 60 == 41 || z % 60 == 49 || z % 60 == 53)) { prime[z] = !prime[z]; } z = 3 * x * x + y * y; if (z <= N && (z % 60 == 7 || z % 60 == 19 || z % 60 == 31 || z % 60 == 43)) { prime[z] = !prime[z]; } z = 3 * x * x - y * y; if (x > y && z <= N && (z % 60 == 11 || z % 60 == 23 || z % 60 == 47 || z % 60 == 59)) { prime[z] = !prime[z]; } } } for (i = 5; i <= sqrt_num; i++) { if (prime[i] == PRIME) { for (j = 1; j * i * i <= N; j++) { prime[j * i * i] = NON_PRIME; } } } printf("2 3 5 "); for (i = 7; i <= N; i++) { if (prime[i] == PRIME) { printf("%zu ", i); prime_num++; } } printf("\n"); printf("prime_num = %zu\n", prime_num); return 0; } |
実行結果は以下になります．同様です．
|
1 2 3 4 |
$ gcc atkin.c $ a.out 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 prime_num = 25 |
アトキンの篩の実装で利用するsqrt関数を知りたいあなたはこちらからどうぞ．
まとめ
C言語で素数の判定方法を紹介しました．
具体的には，エラトステネスの篩（ふるい），エラトステネスの篩を改良したサンダラムの篩とアトキンの篩を解説しました．
素数の判定方法の高速化を知りたいあなたは以下の記事を読みましょう！
素因数分解アルゴリズムを知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
