探索アルゴリズム(Searching Algorithms )

/*
線形探索法による素数探索
*/

#include <stdio.h>

#define   n    25

prime_n[n]={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};

void search(int key){
    int i=0;

    while(prime_n[i] <= key){
       if(prime_n[i] == key){
          printf("素数です。\n");
          printf("探索回数=%d\n", i+1);
          exit(0);
       }
       i++;
    }
    printf("素数ではありません。\n");
    printf("探索回数=%d\n", i+1);
}

int main(void){
    int i;
    int key;
    printf("100以下の自然数を入力してください。\n");
    scanf("%d", &key);

    search(key);

   return 0;
}

/*
二分探索法による素数探索
*/

#include <stdio.h>

#define   n    25

prime_n[n]={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};

void binary_search(int key){
    int i=0;
    int low, high, mid;

    low=0;
    high=n-1;

    while(low <= high){
       i=i+1;
       mid = (low + high)/2;
       if(prime_n[mid] == key){
          printf(""素数です。\n");
          printf("探索回数=%d\n", i+1);
          exit(0);
       }
       else if(prime_n[mid] > key)
          high = mid - 1;
       else
          low =mid + 1;
    }
    printf(""素数ではありません。\n");
    printf("探索回数=%d\n", i);
}

int main(void){
    int i;
    int key;
    printf("100以下の自然数を入力してください。\n");
    scanf("%d", &key);

    binary_search(key);

   return 0;
}

/*
keyと配列の添え字(subscript)を一致させる
*/

#include <stdio.h>

#define   n    101

prime_n[n]={0,0,2, 3,0, 5,0, 7,0,0,0, 11,0, 13,0,0,0, 17,0, 19,
                      0,0,0, 23,0,0,0,0,0, 29,0, 31,0,0,0,0,0, 37,0,0,
                      0, 41,0, 43,0,0,0, 47,0,0,0,0,0, 53,0,0,0,0,0, 59,
                      0, 61,0,0,0,0,0, 67,0,0,0, 71,0, 73,0,0,0,0,0, 79,
                      0,0,0, 83,0,0,0,0,0, 89,0,0,0,0,0,0,0, 97,0,0,0};

void search(int key){

    if(prime_n[key] == 0)
        printf("素数ではありません。\n");
    else
        printf("素数です。\n");
}

int main(void){
    int key;
    printf("100以下の自然数を入力してください。\n");
    scanf("%d", &key);

    search(key);

    return 0;
}

/*
ハッシュ法
*/

#include <stdio.h>

#define   n    49

prime_n[n]={0,0,2, 3, 53, 5,0, 7,0,0, 59, 11, 61, 13,0,0,0, 17, 67,
                      19, 0,0, 71, 23, 73,0,0,0,0, 29, 79, 31,0,0, 83,0,0,
                      37,0,0, 89, 41,0, 43,0,0,0, 47, 97};

void search(int key){
    int h;
    h = key%49;
   
    if(prime_n[h] == key)
       printf("素数です。\n");
    else
       printf("素数ではありません。\n");
}

int main(void){
    int key;
    printf("100以下の自然数を入力してください。\n");
    scanf("%d", &key);

    search(key);

   return 0;
}