1. 计数质数

统计所有小于非负整数 n 的质数的数量。

1.1 迭代法

解题思路：数学问题，用到了两个质数判定性质：
1.一个数n进行因式分解，分解得到的两个数一个>=sqrt(n),另一个<=sqrt
2.一个大于5的质数，一定在6的倍数左右
证明大于5的数的序列是6，6+1，6+2，6+3，6+4，6+5，6*6......6x+1，6x+2，6x+3，6x+4，6x+5...... ,一定不是质数的有 6x+2=2(3x+1),6x+3=3(2x+1),6x+4=2(3x+2),所以6x+1和6x+5有可能成为质数
那么我们再看一下6x+1和6x+5都有哪些情况不是质数；
1.因式分解情况，当x>=2时，6x+1 = 2*3(x-1)+7 6x+5 = 2*3*x+5，由于2，3，5，7都是质数，那么如果2*3(x-1)+7 这个式子需要整除这（x-1）一定时7的倍数，即(6x+1) % 7 !=0时，6x+1这个式子即为质数，同理(6x+5)%5!=0,6x+5为质数。
2.还有一种情况：假设6y+1是质数，那么(6y+1)² = 36y²+12y+1=6(6y²+2y)+1 = 6x+1 ,此种情况的6x+1是不能算做质数的，同理6x+5也有此种情况。
总和两种情况分析，无论拆解和累加，一定不能满足可以整除5,7,...,6x+1,6x+5的情况。
所以我们先减少遍历个数，找到满足6x+1或6x+5的项，然后分别对下面的数{5,7,11,13...sqrt(n)}取余进一步判断是否满足素数。

int countPrimes(int n)
{
    --n;
    if (1 >= n)
        return 0;
    if (2 == n)
        return 1;
    if (4 >= n)
        return 2;
    if (6 >= n)
        return 3;
    int rs = 3;
    int i = 7;
    int step = 4;
    bool isPrime = true;
    while (i <= n) {
        int n_sqrt = (int)sqrt(i);
        for (int j = 5; j <= n_sqrt; j += 6) {
            if (i % j == 0 || i % (j + 2) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            ++rs;
            cout << i << endl;
        }
        i += step;
        if (2 == step)
            step = 4;//6x+5
        else
            step = 2;//6x+1
        isPrime = true;
    }
    return rs;
}

1.2 埃拉托斯特尼筛法

解题思路：此方法并没有教会你怎样判断一个数是不是质数，只是由小到大将不是质数的数值剔除，那么剩下的数就一定是质数，那么怎样剔除呢。
1.首先，我们知道如果一个数不是质数，那么它一定可以拆分成一堆质数的积，即P如果不是质数，那么P=p₁p₂p₃p₄ ... p_n，其中p_n是不可分割,即是质数，所以我们只需要从2开始剔除所有分解因子中含2的数，然后在2之后的剩余队列中找到最小质数，以这个最小质数为基准，剔除与这个最小质数相关的合数。
2.从2开始遍历筛选，每次都取得最小质数，那么在取到剩余队列的最小质数之前，有没有可能落下一个合数呢？不可能，原因如下，由1中可知，如果P是一个合数，那么P=p₁p₂p₃p₄ ... p_n，那么其中的一个质数p_i(1<=i<= n)一定小于P，也就是说P一定是P之前的质数构成的，那么根据动态规划的思想，从2开始剔除合数，当搜索到P时，P一定被之前的质数剔除的过程中剔除了，所以我们挑选剩余队列的最小质数时，在遇到第一个质数之前，是不可能存在一个没被剔除的合数的。
3.那么筛选遍历一定要筛选到n吗？没有必要，因为一个合数因式分解成两个数，这两个数一定是一个<=sqrt(n),一个>=sqrt(n)，我们的主要思想是取到剩余队列中第一个质数，然后剔除后续与质数相关的合数。当我们在选取质数时，选取到一个质数>sqrt(n)，那么由它构成的合数如果想<=n ，另外一个数一定小于sqrt(n)，那么这个合数在之前已经被剔除了，没有必要再二次判断了。
4.那么我们找到了一个质数p，然后向后剔除与其相关的合数，一定要从p+1开始吗？答案是否定的，因为我们不仅仅剔除的是由质数p构成的合数，而是构成这个合数的质数序列中p为最小，这个合数才是需要被我们剔除的，如果p不是这个质数序列中的最小值，那么这个合数已经在之前遍历到那个最小质数时被干掉了！由p组成的最小合数，且组成合数的质数队列中p还是最小，那么这个合数一定就是p*p。
与程序优化相关的注解在代码相应位置体现

算法直观图

 int countPrimes(int n)
{
        --n;//为什么要减1？看题目，这是个坑
        if( n<=1 ) return 0;
        vector<bool> map(n,true);
        map[0] = false;
        map[1] = false;
        int n_sqrt = sqrt(n)+1;//由于sqrt不能整开方时是向下取整，+1 是为了避免访问不到的情况；
        for(int i = 2 ; i <=n_sqrt ;++){
            if(map[i]){//继续遍历时如果是合数，一定已经在之前被剔除了，至于为什么，看我之前的分析，那么往后遍历遇到第一个标记为true的就一定是质数。
                //剔除由此质数构成的合数
                //为什么从i*i开始，看解释4
                for(int j = i*i;j<=n;j+=i){
                    map[j] = false;
                }
            }
        }
        int count = 0;
        for( int i=2 ;i<=n;i++){
            if(map[i])
                count++;
        }
        return count;
}

1.3对比

	迭代法	埃拉托斯特尼筛法
时间复杂度	高，原因是迭代法每一个数是否为质数都需要做一次循环判断	低，除了在寻找最小质数时会对合数位置多一次访问以外，其他位置都仅仅访问一次
空间复杂度	常数	n有多大浪费的空间就有多大
适用场景	n特别庞大时	n值适中有足够的空间
备注	不仅仅适用于本题，还可以适用于判断一个数是不是质数	只适用于本题

1.4 写在本题最后

在理解埃拉托斯特尼筛法时，查阅了网上的一些资料，无一例外都写了应该怎么做，当并没有证明这种方法的合理性，及设计点，如此刷题，有何意义？拿来主义并不可耻，但是仅仅是鹦鹉学舌只会产生垃圾，害人害己，以此警示自己。

---

2. 3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。
你能不使用循环或者递归来完成本题吗？

解题思路：一种比较无耻的做法，先利用程序手算出3的幂在程序中最大的数，计算3的幂可以利用换底公式：log₃^INT_MAX = log^INT_MAX/log³，此式计算出最大3的幂数，然后再利用这个幂数求出3的最大幂数。判断此值是否可以被3整除。
注意：不要忽律3的0次幂

bool isPowerOfThree(int n) {
        if( 1 == n) return true;
        if(3>n) return false;
        int max3 = pow(3,(int)(log(INT_MAX)/log(3)));
        if(0 == max3%n)
            return true;
        return false;
    }

---

3. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解题思路：正常的字符转换直接对应就好，那么符合型字符应该怎样处理？如果遇到I那就判断它的下一位是否为V或X，如果存在那么此时需要的是-1，因为在下一位做加法时会多加1，同理可以处理以X开头的复合字符，以C开头的复合字符。

int romanToInt(string s)
{
    int rs = 0;
    int sSize = s.size();
    for (int i = 0; i < sSize; ++i) {
        switch (s[i]) {
        case 'I':
            if (i + 1 < sSize && ('V' == s[i + 1] || 'X' == s[i + 1])) {
                rs -= 1;
            } else {
                rs += 1;
            }
            break;
        case 'X':
            if (i + 1 < sSize && ('L' == s[i + 1] || 'C' == s[i + 1])) {
                rs -= 10;
            } else {
                rs += 10;
            }
            break;
        case 'C':
            if (i + 1 < sSize && ('D' == s[i + 1] || 'M' == s[i + 1])) {
                rs -= 100;
            } else {
                rs += 100;
            }
            break;
        case 'V':
            rs+=5;
            break;
        case 'L':
            rs+=50;
            break;
        case 'D':
            rs+=500;
            break;
        case 'M':
            rs+=1000;
            break;
        }
    }
    return rs;
}
};