线性筛法

make_prime_n

1. 普通筛法  

	n = 1000000
	arr=[1]*(n+1)
	arr[0]=arr[1]=0
	s = 2
	for i in xrange(2,int(n**0.5)+1):
		if arr[i] == 1:
			for j in xrange(i*i, n+1,i):
				arr[j] = 0
2. 线性筛法  

	#include<iostream>
	using namespace std;    
	const long N = 200000;   
	long prime[N] = {0},num_prime = 0;    
	int isNotPrime[N] = {1, 1};   
	int main()    
	{     
	       for(long i = 2 ; i < N ; i ++)       
	         {            
			if(! isNotPrime[i])               
		 		prime[num_prime ++]=i;  
			//关键处1        
			for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)
	    		{               
			      	isNotPrime[i * prime[j]] = 1;  
		  		if( !(i % prime[j] ) )  //关键处2                  
					break;           
			}        
		}        
		return 0;   
	}