人工知性を作りたい

私が日々、挑戦したことや学んだことなどを紹介していく雑記ブログです。 (新しいAI技術HTM, 専門の音声信号処理, 趣味のアニメ等も書いてます。)

素数判定! プログラミング実装! 【C言語】

f:id:hiro-htm877:20190601191549p:plain

 

f:id:hiro-htm877:20190601202549p:plain

 プログラミング初心者、学生

素数を学んだ。素数ってどこまで続くか気になる!

・授業で素数判定のプログラミング課題が出た!

 どうしたらいいの〜〜〜!

 

そんな方の疑問に答えます。

 

コードが知りたい方は目次のソースコードへ飛んでください!

本記事のテーマ

【完全初心者向け】素数判定、C言語プログラミング!

素数とは

素数とは「1より大きい整数で、1と自分自身でしか割り切れない数」のこと。

英語では Prime Numberという。

※「割り切れる」とは自然数で割ったときの「あまり」が0のこと

1〜99の素数判定

アルゴリズム

判定する数をnとすると、

1. nを2〜nまでの数で割る

2. 余りが0の時、素数ではない!

3. 余りが0より大きい時、素数

さらに実行速度の短縮のために

1’. nを2〜n/2、までの数で割る

 以上のアルゴリズムを元にC言語プログラミングを組んでいきます!

素数判定、実装!

判定方法は、 

1. 配列histogramを宣言する

2. histogramの要素を階級とし、同じ階級の数字を数える

素数判定コード

・2〜n/2までの自然数で割る

for(i=2; i<= (number>>1); i++){

 ・number>>1でn/2を実現

 ・割り切れた時は素数じゃないので、breakしてfor文を抜ける

 

素数判定(0:素数、1:素数じゃない)

if(i < ((number >> 1)+1)){

 ・前のfor文をbreakで抜けたのかどうかの確認

 ⇨iがfor文の終了判定値(number>>1)+1より小さければ、breakで抜けた判定

 ⇨つまり、割り切れているので素数ではない!

 

int prime_number(int number){
    int i;
    //0と1は例外処理を行う
    if(number == 0 || number== 1){
        return 1;
    }
    //2〜n/2までの自然数で割る
    for(i=2; i<= (number>>1); i++){
        if(number % i == 0){
            break;
        }
    }
    //素数判定(0:素数、1:素数じゃない)
    if(i < ((number >> 1)+1)){
        return 1;}
    else{
      return 0;}
}
出力 

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

完成です!

99以上の数値を調べたい時は、mainのfor文をいじって下さい!

main文を含む全ソースコードは以下に示します。 

ソースコード

#include <stdio.h>
int prime_number(int number);
void enshu0604(void);

int main() {
    enshu0604();
    return 0;
}

void enshu0604(void){
    int i;
    for(i=0; i<99; i++){
        if(prime_number(i) == 0){
            printf("%3d", i);
        }
    }printf("\n");
}
int prime_number(int number){
    int i;
    //0と1は例外処理を行う
    if(number == 0 || number== 1){
        return 1;}
    
    //2〜n/2までの自然数で割る
    for(i=2; i<= (number>>1); i++){
        if(number % i == 0){
            break;}
    }
    //素数判定(0:素数、1:素数じゃない)
    if(i < ((number >> 1)+1)){
        return 1;
    }
    else{
        return 0;
    }
}