Cod sursa(job #627516)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 30 octombrie 2011 03:05:02
Problema Ciurul lui Eratosthenes Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.5 kb
#include<cstdio>
#include<vector>
using namespace std;

int main(){
	freopen("ciur.in", "r", stdin);
	freopen("ciur.out", "w", stdout);
	
	int i, j, N, nr=1, k;	
	scanf("%d", &N);
	
	int jum = N % 2 == 0 ? N / 2 - 1 : N / 2;
	vector <bool> v; 
	
	for (i = 1; i <= jum+1; i++) v.push_back(true);
	
	for (i = 1; i <= jum; i++)
		if (v[i] == true){
		nr++;
		k = i * 2 + 1;
		for (j = 3 * k; j <= N ; j += 2*k)
			v[j / 2] = false;
		}
	
	printf("%d\n", nr);
	fclose(stdout);
	return 0;
}