Prime

gistfile1.c

#include "stdio.h"
#include "math.h"

#define MAX 100000000
int prime[MAX]; //在堆上，自动初始化为0


void initPrimes(){
	int i, j;
	prime[0] = prime[1] = -1; // not prime number
	for(i=2; i<MAX; i++){
		if(prime[i] == 0){ // not confirmed
			prime[i] = 1; // is prime
			for(j=i+i; j<MAX; j+=i){ // use add instead of multi
				prime[j] = -1; // not prime number
			}
		}
	}
}
/**
//除法判断
int isPrime(const int n){
	int i;
	for(i=2; i<=sqrt((double)n); i++){
		if(n%i == 0)
			return 0;
	}
	return 1;
}
**/

int main(){
	int i, count, sep=10;
	initPrimes();
	for(i=1, count=0; i<MAX; i++){
		if(prime[i] == 1)
			count ++;
		if(i%sep == 0){
			printf("%d/%d=%5.3f\n", count, i, 1.0*count/i);
			sep *= 10;
		}
	}
	getchar();
}