几种常见的算法

1.埃氏筛选法（求素数）

      埃氏筛选法的思想:首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数。

       基本思路：

           1. 首先将0、1排除：

           2. 创建从2到n的连续整数列表，[2,3,4,…,n]；

           3. 初始化 p = 2，因为2是最小的素数；

           4. 枚举所有p的倍数(2p,3p,4p,…)，标记为非素数（合数）；

           5. 找到下一个 没有标记 且 大于p 的数。如果没有，结束运算；如果有，将该值赋予p，重复步骤4;

           6.  运算结束后，剩下所有未标记的数都是找到的质数。

           步骤4中可以进行优化：

                   可以不用从2p开始排除，而是直接从 p的平方开始。原因是[0, √N ]范围内很多>√N 的数其实是[0,√N ]范围内数的倍数，而>√N 且非[0,√N ]范围内数的倍数的，都是质数，所以我们没必要从2p开始，直接从平方开始。

                   对于步骤5，当平方>n的时候停止.

             

 

 2.二分查找

     思路：二分查找首先要确保值是有序的，其次 将中间的值和要寻找的值(target)进行比较，如果target > mid,证明要寻找的值在右侧，left = mid+1，否则   right = mid-1，(right初始化为length-1)

     代码：

              

 

      寻找左侧边界的二分搜索：

               

       寻找右侧边界的二分搜索

               

 

3.动态规划

       动态规划三个重要的概念：

               最优子结构      边界         状态转移公式

       DP是一种思想，一种“大事化小，小事化了”的思想。带着这种思想，DP将会成为我们解决问题的利器。

       但是这两层for循环，复杂度O(n*n)，可以用二分查找+DP  ,复杂度就会降低