列印前N個素數

題目：列印前N個素數，不需要考慮大數和溢出 思路：從2開始，依次檢測後續的每個數，若為素數，計數加1，直到計數到N。 分析：問題複雜度的瓶頸在于判斷一個數是否為素數。鑒于前面的素數已經找出，可以将所有找出的素數儲存下來，在判斷一個數x是否為素數時，隻需判斷該數x是否能整除 [2，sqrt(x)]内的所有 素數即可。

/*  
* 列印前N個素數  
* 不需要考慮大數和溢出的情況  
*  
*/  

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

void print_prime(int N)  
{  
	if (N < 1) return;  
	std::vector<int> primes;  
	int num = 2;  
	int count = 1;  
	primes.push_back(num);  
	printf("%d ", num);  

	while (count < N) 
	{   
		bool isPrime = true;   
		++ num;   
		int sqr = (int)std::sqrt((float)num);   
		for (std::vector<int>::iterator iter = primes.begin();   
			iter != primes.end() && *iter <= sqr;   
			++ iter) 
		{  
			if (num % *iter == 0)
			{   
				isPrime = false;   
				break;   
			}   
		}  
		if (isPrime) 
		{   
			++ count;   
			primes.push_back(num);   
			printf("%d ", num);   
		}   
	}  
} 
           

PS: Google，2013，校招，筆試