Cod sursa(job #374653)

Utilizator Balmus_MaximBalmus Maximilian Balmus_Maxim Data 17 decembrie 2009 17:33:25
Problema Ciurul lui Eratosthenes Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.39 kb
#include <stdio.h>

int main()
{
	int n,i,v[250010],j,m=0;
	freopen("ciur.in","r",stdin);
	freopen("ciur.out","w",stdout);
	scanf("%d",&n);
	v[0]|=1;
	v[0]|=(1<<1);
	for(i=1;i<=n;i++){
		if((v[i/8]&(1<<(i%8)))==0){
			for(j=i+i;j<=n;j+=i){
				v[j/8]|=(1<<(j%8));
			}
		}
	}
	for(i=1;i<=n;i++){
		if((v[i/8]&(1<<(i%8)))==0){
			m=m+1;
		}
	}
	printf("%d",m);
	return 0;
}