204 计数质数
思路
1.暴力法。两层循环。O（n1.5）,因为内层可以写为（0，n0.5）。但是结果超时了。
def countPrimes(self, n: int) -> int:
if n<2:
return 0
counts = 0
temp =1
for num in range(2,n):
temp =1
for i in range(2,int((num)**0.5)+1):
if num % i == 0:
temp =0
break
counts = counts+temp
return counts
2.其实内层循环没必要从2，3，4，5。。。一直到根号n，可以直接判断素数，2，3，5，7…直到根号n。
所以需要保存之前的素数，占用空间节省时间。时间复杂度 为O(n*(1/2 +…))
后续无法计算：很难计算不同的n值需要判断几个素数才能判断。
但这个复杂度确实比标准解答的多。
竟然还是超时了。最后一个n=1500000超时
def countPrimes(self, n: int) -> int:
if n<2:
return 0
temp = 1
primes = []
for num in range(2,n):
temp =1
for i in primes:
if i*i > n:
break
if num % i == 0:
temp =0
break
if temp ==1:
primes.append(num)
return len(primes)
3.就直接看答案了，发现用排除法。
首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。
然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。
该算法的时间复杂度比较难算，显然时间跟这两个嵌套的 for 循环有关，其操作数应该是：n/2 + n/3 + n/5 + n/7 + …
= n × (1/2 + 1/3 + 1/5 + 1/7…)括号中是素数的倒数。其最终结果是 O(N * loglogN)
作者：labuladong
算法名称：
埃拉托斯特尼筛法，简称埃式筛，也叫厄拉多塞筛法：
要得到自然数n以内的全部质数，必须把不大于根号n的所有质数的倍数剔除，剩下的就是质数。
def countPrimes(self, n: int) -> int:
if n<2:
return 0
primes = [1 for i in range(n)]
sums=0
for i in range(2,n):
if primes[i] == 1:
for j in range(2*i,n,i):
primes[j] = 0
sums =sums+1
#减2是0和1没赋值零。本身有循环，相比于手动加和，用sum函数会变慢。
#return sum(primes)-2
return sums
4.然后空间上可以用比特表（Bitmap）算法来代表1/0，没必要用数字。但是二进制我知道，位图什么的还不太懂，先暂时放在这。
374. 猜数字大小
随机到375，先把一系列的374做了
标准的二分法题
def guessNumber(self, n: int) -> int:
#上下限a，b
a=1
b=n
k0 = 0
while True:
k = (a+b)//2
#最后上下限相差1，k值一直不变，会卡死在循环里，加个手动判断
if k ==k0:
k= k+1
if guess(k) ==1:
a= k
elif guess(k) == -1:
b= k
elif guess(k) == 0:
break
k0 = k
return k
2.官方题解的优化1，不手动判断是否会卡死，而是给上下限加上1的偏移量。
ps:但是时间反而下降了。。。20ms降到了28ms，可能是不加1操作更快。
def guessNumber(self, n: int) -> int:
a=1
b=n
while a<=b:
k = (a+b)//2
if guess(k) ==1:
a= k+1 #1个偏移量
elif guess(k) == -1:
b= k-1
elif guess(k) == 0:
break
return k
3.还提到了三分查找，但二分绝对是最快的，log3n需要判断两次，2*log3n大于log2n。
ps：三分可以优化成1/3情况下判断一次，2/3情况下判断两次，均值为5/3。乘上log3n 仍然是比二分法慢。
5/3 *log3n = 5/3 * log2n /log23 ≈ log2n * 1.666666/1.5849625 >log2n
4.一个小点：写成这样而不是（a+b）/2，一定程度上能避免溢出。
int mid = low + (high - low) / 2;