今日の試験の問題は覚えていませんが、問題が公開されたら分析します。今日はクラシックなアルゴリズムである素数の計算方法について話します。多くの人が総当たり法を覚えていると思います。つまり、数を 1 から N の平方根以下の数で割り続け、結果を得る方法です。アルゴリズムの時間計算量は O (N^2) で、最適化されたアルゴリズムは O (N * sqrt (N)) です。クラシックなアルゴリズムについては説明しませんが、初心者の方でわからない場合はコメントを残すか、私に連絡してください。
以下は素数の計算方法のクラシックなコードです。
/* 素数の計算方法、総当たり法
*author CG
*2008 12 21
* 時間計算量 O (N * sqrt (N))
*/
#include"stdio.h"
#include"math.h"
#define N 200/* テストデータの定義 */
int main() {
int i , j;
for(i = 2 ; i <= N ; i++) {
for (j = 2 ; j <= (int) sqrt (i) ; j++){/*j が sqrt (i) 以下の場合に比較 */
if(i % j == 0){
break;
}/*if*/
}/*for*/
if (j> (int) sqrt (i)){/* 条件に合致するか？*/
printf ("%-10d",i);/* 出力 */
}/*if*/
}/*for*/
return 0;
}/*main*/
以下は現在よく使用されている素数の計算方法です。もちろん、より優れたアルゴリズムでは「フェルマーの小定理」を使用して、素数の確率分布を実現し、ほぼ線形のアルゴリズムの計算量を得ることができますが、今日は説明しません。興味がある場合は、引き続き私をフォローしてください。最近時間がある場合は、コードを掲載します。
さて、今日の主役は「篩法による素数の計算」です。原理は既存の配列データから必要な素数を選び出すことです。N サイズの空間が必要で、N は求める素数の範囲です。クラシックなアルゴリズムと比較して無駄が多いですが、効率は高く、O (N * LogN) です。大規模な素数の計算に適していますが、空間の無駄も客観的に存在します。
原理：インデックス j=2,0,1 の場合を除外し、j のすべての倍数を除外し、次に j+1 を除外し、j=N まで除外します。
具体的なアルゴリズムは以下の通りです。
/* 篩法による素数の計算
*author CG
*2008 12 21
* アルゴリズムの計算量 O (N * LogN)
*/
#include "stdio.h"
#define N 200/* 最大数の定義 */
int main() {
double s , t;
int num[ N + 1 ] = {0};
int j = 2 ;/* 開始数を 2 に定義 */
int i ;/* カウンタ */
for(i=2 ; i<=N ; i++) {
num[i] = 1;
}
while(j<=N) {
for(i=2 ; ij<=N ; i++) {
num[ij] = 0;
}
j++;
while(num[j]==0) {
j++;
}
}
for(i=2 ; i<=N ; i++) {
if(num[i]==1) {
printf("%-10d",i);
}
}
return 0;
}