メモ

２より大きい偶数は素数でない。→それ以上の偶数を対象外にする。
３以上の素数は２より大きい２の倍数で割り切れない。→奇数のみで割る。
３,5,7…で割り切れない整数は、３,5,7…の倍数でも割り切れない。→ある整数より小さい素数での除算において割り切れなければ素数。なので調べたい整数を得られた素数で割ればよい。
調べたい整数の平方根以下の素数での除算において一度も割り切れることがなければ素数。

#include<stdio.h>

int main(void){
  int i,no,counter;
  int ptr=0;    /*得られた素数の数*/
  int prime[500];  /*素数を格納するための配列*/

  prime[ptr++]=2;   /*2は素数*/
  prime[ptr++]=3;   /*3は素数*/

  for(no=5; no<=1000; no +=2){
    int flag =0;
    for(i=1; counter++, prime[i]*prime[i]<=no; i++){
      counter++;
      if(no % prime[i]==0){  /*割り切れると素数じゃない*/
	flag=1;
	break;      /*割り切れた時点で終了*/
      }
    }
    if(!flag)   prime[ptr++]=no;  /*割り切れないと素数。素数を配列に入れる*/
  }

  return 0;
}