eratosthenes.cc

#include <vector>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;

vector<int>* eratosthenes(int n) {
  int max = (int) sqrt((double)n);
  //printf ("m: %d\n",max);
  vector<int> seive(n+1);
  for(int i=0;i<=n;i++) {
    seive[i] = 1;
  }

  for (int i=2;i<=max;i++) {
    if (seive[i] == 1) {
      for (int j=i*2;j<=n;j+=i) {
	seive[j] = 0;
      }
    }
    
  }
  vector<int>* primes =  new vector<int>();
  for (int i=2;i<=n;i++) {
    if (seive[i]==1) {
      //printf ("%d is prime\n",i);
      primes->push_back(i);
    }
  }
  
  return primes;
}


int main() {
  int n;
  vector<int> in;
  while(cin>>n) {
    in.push_back(n);
    //printf("n %d\n", n);
  }
  int max = *max_element(in.begin(), in.end());
  printf("max %d\n", max);

  vector<int>* primes = eratosthenes(max);
  
  int count = 0;
  for (int i=0;i<in.size();i++) {
    for (int j=0;j<primes->size();j++) {
      if (in[i] == (*primes)[j]) {
	count++;
	break;
      }
    }
  }

  printf("%d\n",count);
  
  return 0;
}