Description:

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

s思路： 1. 先看看這道題的邊界是什么。肯定需要檢查每個數i是否質數，而檢測是否質數則需要檢測小于i的數和i能否整除。這樣，復雜度就是o(n*n). 2. 這么做如何？只能說這個邊界太粗了，沒有壓縮得很仔細，還有空間可以壓縮，或者說有很多重復的計算量。比如：我們檢測到7是prime number,那么49呢？為了檢測49是否是Prime,需要從2-48來除，看是否整除，當除到7的時候發現能整除，因此不是prime。可以明眼人，一眼就看出49不是prime,為啥要費這么大氣力來一個一個嘗試，因為我們知道7是因子。這就需要打破思維里的枷鎖了，不用除法，因為49=7*7，所以當我們發現7是prime,那么7的所有倍數都不是prime，因此49也不是prime，完全沒必要從2開始嘗試。或者說，這里面思維的變化是，從做除法變成做乘法，這也是應該推廣的思維方式：一個方法繁瑣，通常這個方法的逆方法就很容易。比如：當我們從左側遍歷vector，發現很多case需要處理，理解起來也不方便，那么不妨讓思維來個反轉，從右邊遍歷。這個思維模式在我們習慣二分的世界里，通常可以轉復雜為簡潔，立竿見影！ 如上圖：看問題都有兩個相反的角度，而通常容易看到的角度如果有很多重復運算，不簡潔，很多corner case，很多不smooth的地方，很多暗溝，很多分離的地方，這是因為我們碰巧就是從一個正常的角度看見了這個問題。這個時候，就需要能轉念，轉念才能看到強大的normal view背后的opposite view，在那兒就沒有這么繁復的，重復的操作。因此，表面看是從除法變成乘法，從被動的嘗試變成主動的標記，實際上，是思維從normal view轉到相反的角度看到了opposite view。因此，越是發現思維里的方法很繁復、很細瑣，那就越說明這個強大的想法背后肯定藏著有一個簡單的美妙的方法，這需要上升到一個信念才可以開發到背后的opposite view! 3. 回到具體的方法上去。normal view看到的是：檢查每個數是否是prime，每個數的檢查就是從2開始枚舉看是否都不能整除，問題：每次檢查都是同頭檢查，沒有利用數與數間的關系，把連續的數看成分離的數。而opposite view看到的是：一旦發現一個prime,那么就主動去給這個prime的所有倍數標記為非prime，以后就不用再判斷是否prime，這就充分利用“連續”這個特點，同時把查詢變成了廣播。這里特別強調：普通的查詢是指所有的可能都嘗試，無論別人是否嘗試過，因為普通的查詢來說，每次運算相互獨立，并不相互通信，導致重復運算很多；廣播則很好的避免了這一點：一旦掌握了某個信息，就把這個信息廣播出去讓相關的節點都能知道這個信息，對后面要進行的運算做標記，這個廣播的作用，就是連接運算和運算之間的橋梁，防止重復計算。因此，在opposite view的角度里，存在broadcast的方法，避免了重復計算，因此復雜度從查詢的o(n^2)降低到o(n)。如下圖。回想一下，這個broadcast就是dp的思想。