/*------------------------------
素数を求める
[考え方]
素数かどうか判定したい数をＡとおく。
(1)１とＡ以外の数で割り切れなかったら素数である。
(2)数学的に√Ａまでの数で割り切れなかったら素数であることが分かっている。
(3)エラストテネスのふるいという方法を使えば高速で素数を求めることが出来る。

[素数かどうかの判定法]
５が素数かどうか判定しよう。
(1)２で割ってみる。割り切れない。
(2)３で割ってみる。割り切れない。
(3)４で割ってみる。割り切れない。
よって５は素数。

しかし、まだ改善の余地があります。
(2)(3)の処理は必要ありません。なぜなら、３と４は√５より大きい数だからです。
考え方の(2)を参照して下さい。

そういうことで、
・２で割ってみる。割り切れない。
だけの処理で５が素数ということを判定することが出来ます。


[エラストテネスのふるい]
１００までの素数を列挙してみよう。
(1)１〜１００までの数をリスト化します。そして１から順番に見ていきます。
(2)１は素数ではないので１を消します。
(3)２は素数なので残します。そして２より大きい２の倍数（4,6,8,...,100)を消去。
(4)３は素数なので残します。そして３より大きい３の倍数（6,9,12,...,99)を消去。
(5)５は素数なので残します。そして５より大きい５の倍数（5,10,15,...)を消去。
(6)７は素数なので残します。そして７より大きい７の倍数（7,14,21,...)を消去。
残った数字が素数です。


エラストテネスのふるいで用いた
         「自分自身の数のルート以下の素数で割り切れなければ素数」
                                               というミラクルな定理の証明
例えば、101が素数かどうか調べる時は、101のルートの整数値を取って10。
その10までの素数「2,3,5,7」で101を割ることができないから101は素数となります。
それで、何故ルート以下の数を調べればOKなのかを証明します。

まず、素数ではない数を考えます。この数をＸとおきます。
Ｘは素数ではないので
Ｘ＝Ａ×Ｂ　（Ａ＞＝２、Ｂ＞＝Ａ、Ａは素数）
とおけます。
そこでＡの上限を考えます。
ＡはＢ以下なので、Ａが最大の時を考えるとＡ＝Ｂとなります。
つまりＸ＝Ａ×Ａとおけます。
よってＡ＝ルートＸとなり、Ａの範囲は２＜＝Ａ＜＝ルートＸとなります。

・・・下手な証明ですが、まぁいいでしょう。

  -----------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 1000000 /* エラストテネスで求める最大の数 */

void prime_number1(void); /* 素数判定 */
void prime_number2(void); /* エラストテネスのふるい */

int main(void)
{
 int num;
 puts(
  "#==================#\n"
  "#  素数モトメール  #\n"
  "#==================#\n"
  "\n"
  "[1] 素数かどうか判定\n"
  "[2] エラトステネスのふるいで素数を列挙\n");

 scanf("%d",&num);
 if(num == 1) prime_number1();
 else if(num == 2) prime_number2();
 return 0;
}

/* エラストテネスのふるい */
void prime_number2()
{
 int num,i,j,*x;
 x = (int *)malloc(sizeof(int)*(MAX+1));
 if(!x){puts("メモリ確保が出来ませんでした。終了します。");return;}

 printf("素数をいくつまで求めますか？");
 scanf("%d",&num);

 /* 初期化 */
 for(i=0;i<=num;i++){
  x[i] = 0;
 }

 /* エラストテネスのふるい */
 for(i=2;i<=(int)sqrt(num);i++){
  for(j=i*2;j<=num;j+=i){
   x[j] = 1;
  }
 }

 /* 表示 */
 for(i=2;i<=num;i++){
  if(x[i] == 0){
   printf("%d ",i);
  }
 }
 free(x);
}

/* 判定 */
void prime_number1()
{
 int i,flag=0,x;

 printf("素数かどうか判定します。数を入力して下さい。-->");
 scanf("%d",&x);

 if(x == 1)flag = 1;/* １は素数ではない */
 else{
  for(i=2;i<=(int)sqrt(x);i++){
   if(x % i == 0){
    flag = 1;
    break;
   }
  }
 }

 if(!flag){
  printf("%dは素数でんがな。\n",x);
 }else{
  printf("%dは素数じゃないじゃん。\n",x);
 }
}