/*素数検索（”ふるい”アルゴリズム）
 *エラトステネスのふるいで検索します
 *ただし、配列を使うため10万程度までしか計算できないこともあります。
 */
#include <stdio.h>

int main()
{
  long count,count2,end;
  printf("enter...>");
  scanf("%ld",&end);
  long num[end+2];
  for (count=0;count < end;++count)
    num[count]=0;
  for(count=2;count < end;++count){
    for(count2=count*2;count2 < end;count2=count2+count)
      num[count2]=1;
  }
  for(count=2;count < end; ++count){
    if(num[count]==0)
      printf("%ld\n",count);
  }
}