【LeetCode】204. Count Primes

问题描述

Description:

Count the number of prime numbers less than a non-negative number, n.

点击查看问题

问题分析

筛选法求素数，参考这篇文章【算法】普通方法和筛选法求素数，这道题用普通方法求素数会超时，只能用筛选法。

代码

class Solution {
public:
    int countPrimes(int n) {
    	if(n<=1) return 0;
    	n--;
    	bool val[n];
    	for(int i=0;i<n;i++) {
	    	val[i] = true;
	    }
		val[0] = false;
		for(int i=1;i<n;i++) {
			if(val[i]==false) continue; 
			// 判断 i+1 是否为素数
			int tmp = i+1;
			bool isPrime = true;
			for(int j=2;j*j<=tmp;j++) {
				if(tmp%j==0) {
					// 不是素数 
					isPrime = false;
					break;
				}
			}
			if(isPrime) {
				// 将这个素数所有的倍数都设置为 false
				for(int j=tmp+tmp;j<=n;) {
					val[j-1] = false;
					j+=tmp;
				} 
			}
		}
		int count = 0;
		for(int i=0;i<n;i++) {
			if(val[i]) {
				count++;
			}
		}
    	return count++;
    }
};