Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
本题要求从1~n共有多少个素数。Hint里一步步深入写得非常详细了，简要概括一下，有两种方法，一种是常规的从1~n一个个判断是否为非数，另一种是比较巧妙的Hash方法。 常规方法。首先看看判断一个数n是否为素数的方法，因为如果n为合数，则n可以分解为p×q，又n=p×q=(√n)×(√n)，假设p是较小数的话，则p≤(√n)。所以我们只需要从2~(√n)判断能否被n整除，时间复杂度为O(n0.5)。从1~n都需要判断是否为素数，所以总的时间复杂度为O(n1.5)。 完整代码如下：
class Solution {
private:
bool isPrime(int x)
{
if (x <= 1)
return false;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0)
return false;
}
return true;
}
public:
int countPrimes(int n)
{
int ans = 0;
for (int i = 1; i < n; ++i) {
if (isPrime(i))
++ans;
}
return ans;
}
};本代码提交TLE，在n很大的时候无法通过测试。
后来看了Hint，解法还是很巧妙的。如果一个数n是素数，则n的倍数肯定不是素数了，比如2是素数，则4=2*2、6=2*3、8=2*4…这些数肯定就不是素数了。所以我们可以建立一个1~n的Hash表，表示一个数是否为素数。初始的时候Hash[1~n]=true。然后从2开始，如果Hash[i]为true，说明i是素数，则2*i, 3*i,…都不是素数了，即Hash[2*i], Hash[3*i]..=false。如果Hash[i]为false，说明i不是素数，则i可以分解为i=p*q，使得p（或q）为素数，则之前测试p时，已经把p的所有倍数都置为false了，而i的倍数肯定也是p的倍数，所以不需要对i的倍数再置false了。
循环的终止条件是i>(√n)，和第一种解法的分析一样，如果某个合数x大于(√n)，则其肯定有一个素因子i是小于(√n)的，所以在测试i时，就已经把x置为false了。
另外对于素数i，我们之前分析的是要把所有2*i, 3*i…都置为false。其实这里也可以优化，我们可以从i*i开始置为false，而不需要每次都从2*i开始。比如i=5，常规是要把所有2*5, 3*5, 4*5, 5*5,…都置为false，但其实2*5, 3*5, 4*5都已经被之前的素数2或3置为false了。所以每次我们只需要从i*i开始，下标以i递增的置为false就好。（从i*i到i*i+(i-1)之间的合数被比i小的合数置为false了）总的来说，这一题加速的技巧很多，完整代码如下：
class Solution {
public:
int countPrimes(int n)
{
vector<bool> mark(n, true);
for (int i = 2; i * i < n; ++i) {
if (!mark[i])
continue;
for (int j = i * i; j < n; j += i) {
mark[j] = false;
}
}
int ans = 0;
for (int i = 2; i < n; ++i)
ans += (mark[i] ? 1 : 0);
return ans;
}
};本代码提交AC，用时29MS。
对于函数$$f(x)=x^2-num$$，$$f'(x)=2x$$，所以牛顿递推式为$$!x_{n+1}=x_n-\frac{x_n^2-num}{2x_n}=(x_n+num/x_n)/2$$
所以我们可以初始代入$$x_n=num$$，然后不断用牛顿法，直到x*x<=num时，如果x*x==num，则num为完全平方数，否则不是。
关于牛顿法用于开放的原理介绍，