def prime(n):
成都创新互联公司专注于广水企业网站建设,响应式网站,商城网站建设。广水网站建设公司,为广水等地区提供建站服务。全流程按需网站制作，专业设计，全程项目跟踪，成都创新互联公司专业和态度为您提供的服务
if n=2:
return []
result=[False,False]+[True]*(n-2)
for i in range(len(result)):
if result[i]==True:
for j in range(2*i,len(result),i):
result[j]=False
return [i for i in range(len(result)) if result[i]==True]
def bi_search(prime,primelist,start,end):
if startend :
return -1
mid=(start+end)//2
if primelist[mid]==prime:
return mid
elif primelist[mid]prime:
end=mid-1
else:
start=mid+1
return bi_search(prime,primelist,start,end)
if __name__=='__main__':
n=int(raw_input())
primelist=prime(n)
num=raw_input()
while num:
num=int(num)
index=bi_search(num,primelist,0,len(primelist)-1)
print(index)
num=raw_input()
要判断一个list中是否存在你要的东西，可以用 value in list 的方式或者 list.index(value), 具体python内部实现用的什么算法。。。自己研究吧。
二分查找： 又称折半查找 ，输入一个有序的元素列表（必须是有序的）， 将列表中间位置记录的元素与查找元素比较， 如果查找的元素包含在列表中， 则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的元素大于查找元素，则进一步查找前一子表，否则进一步查找后一子表，重复以上过程，直到找到满足条件的记录，使查找成功， 二分查找 返回其位置； 或直到子表不存在为止，此时查找不成功 ，返回None。
二分查找算法要求 ： .必须是有序列表；
二分查找算法时间复杂度： O(log n)
二分查找算法优点： 比较的次数少，查找速度快，平均性能好，占用系统内存较少。
def binary_search(list,item):
low = 0
high = len(list) - 1
while low = high:
mid = int((low + high)/2) # 整除计算也可用 mid = (low + high)//2
guess = list[mid]
if guess == item:
return mid
if guess item:
low = mid + 1
else:
high = mid - 1
return None
my_list = [1,3,5,6,8,7,9,12,18,45]
print (binary_search(my_list,2))
print (binary_search(my_list,12))
