プログラミング初心者、学生
・授業で素数判定のプログラミング課題が出た!
どうしたらいいの〜〜〜!
そんな方の疑問に答えます。
コードが知りたい方は目次のソースコードへ飛んでください!
本記事のテーマ
素数とは
素数とは「1より大きい整数で、1と自分自身でしか割り切れない数」のこと。
英語では Prime Numberという。
※「割り切れる」とは自然数で割ったときの「あまり」が0のこと
1〜99の素数判定
アルゴリズム
判定する数をnとすると、
さらに実行速度の短縮のために
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文を抜ける
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;
}
}