APJ Volume0 0044: Prime Number Ⅱ

/******************************
*  2012/07/09                 *
*  AOJ_Volume0_0044           * 
*  Prime_NumberⅡ             *
*  crane                      *
*******************************/


#include<iostream>
#include<cmath>
using namespace std;

#define MAX_N 50023
bool field[MAX_N];
int prime[MAX_N];
int main(){
    for(int i=2; i<MAX_N; i++){
        field[i] = true;
        prime[i] = 0;
    }

    int count = 0;
    field[0] = false;
    field[1] = false;
    for(int i=2; i<MAX_N; i++){
        if(field[i]){
            prime[count] = i;
            count++;
            for(int j=i*2; j<MAX_N; j+=i){
                field[j] = false;
            }
        }
    }
   


    int n;
    while(cin >> n){
        int a=0;
        for(int i=0; i<MAX_N; i++){
            if(prime[i] < n) a=prime[i];
            if(n < prime[i]){
                cout << a << " " <<  prime[i] << endl;
                break;
            }
        }

    }

    return 0;
}

AOJ Volume0 0009: Prime Number

素数テーブルの作成にはエラトステネスの篩を用いる。

/********************************
*    2012/03/21                
*    AOJ Volume0 0009          
*    Prime Number              
*    crane                     
*********************************/

#include<cmath>
#include<iostream>
using namespace std;
#define MAX_N 1000000

void prime();

bool field[MAX_N];

int main(){
 prime();

 int input=0;
 while(cin >> input){ //6桁以下の正の整数
  int result = 0;
  for(int i=0; i<=input; i++)
   if(field[i]) result++;
  cout << result << endl;
 }
 return 0;
}


/*******エラトステネスのふるい********/
void prime(){

 field[0] = false;  field[1] = false;
 for(int i=2; i<MAX_N; i++) field[i] = true;

 for(int i=2; i<sqrt((double)MAX_N)+1; i++)
  if(field[i])
   for(int j=i*2; j<MAX_N; j+=i)
    field[j] = false;
}