C言語で素数判定 - エラトステネスの篩

情報数学のレポートの問題で、8桁までの素数判定プログラムを作成。

エラトステネスの篩の考え方を用いて、計算を効率化しました。

コードは、以下のとおり。

#include<stdio.h>
#include<time.h>

#define MAX 99999999 // 8桁の最大数

void FlagBuild(int arr[MAX], long int n);
void FlagDelete(int arr[MAX], long int n, long int tag);

int area[MAX] = {0};

int main(void){

  long int num;
  long int k = 0;
  int ct = 0;
  clock_t start, end;
  double time;

  // 素数判定する数字の入力 
  printf("素数判定する数字を入力してください:");
  scanf("%ld", &num);

  start = clock();

  // 0 か 1 が入力された場合、メッセージの出力
  if ( num == 0 || num == 1 ){
      printf("%ld は素数ではありません.\n", num);
      return 0;
  }

  // 2 ～ num-1 の数にフラグを立てる
  FlagBuild(area, num);

  // 判定
  for ( k = 2; k < num; k++ ){
      if ( area[k] == 1 ){
          if ( num % k == 0 ) {
              // 反復の打ち切り
              ct++;
              break;
          } else {
              // k の倍数のフラグを削除
              FlagDelete(area, num, k);
          }

      }
  }

  // メッセージの表示
  if ( ct == 0 ) { printf("%ld は素数です.\n", num);}
  else { printf("%ld は素数ではありません.\n", num); }

  end = clock();
  time = (double)(end - start) / 1000;

  puts("");
  printf("処理時間:%.3f[s]\n", time);

  return 0;
}

void FlagBuild(int arr[MAX], long int n){

  long int k;

  // 2 ～ n-1 の数にフラグを立てる
  for ( k = 2; k < n; k++ ){
      arr[k] = 1;
  }
}

void FlagDelete(int arr[MAX], long int n, long int tag){

  long int k;

  // 倍数値のフラグを削除
  for ( k = tag; k < n; k+= tag ){
      arr[k] = 0;
  }

}