[Cで]天下一プログラマコンテスト2012予選C-A

天下一プログラマコンテスト2012予選Cの問題を少しやってみたので書いておく．

問題文

素数とは、1 と自分自身以外に正の約数を持たない、1 以外の自然数のことをいいます。

自然数 n が与えられるので、 n よりも小さい素数の数は何個存在するかを求めてください。

n

11

4

100

25

10000

1229

#include<stdio.h>

int prime(int tester);

int main(void){
int input;
int count=0;
int now=2;
scanf("%d\n",&input);
for(;now<input;now++){
if(prime(now)){count++;}
}
printf("%d\n",count);
return 0;
}
int prime(int tester){
int count=2;
if(tester==2){return 1;}
else{
for(;count<tester;count++){
if(tester%count==0){return 0;}
}
return 1;
}
}

これで通りました．

ちょっと解説してみる．

int prime(int tester);

で宣言をしておく．

そしてメイン関数で2から入力された数までの素数をカウントしている．

int prime(int tester)の中身は純粋な素数判定プログラム．

素数はその数(tester)と1以外では割り切れない数であるので，

2からtester未満の数でtesterを割った時に割り切れないということと同じである．

1が返り値であればtesterは素数．0が返り値であればtesterは素数でないということになっている．

javaとかは余裕があったらまた書いてみる．