每日kata~05~gaps in prime~埃氏筛法

题目：

https://www.codewars.com/kata/561e9c843a2ef5a40c0000a4/train/python
言简意赅的说，就是求区间内是否有gap有n的素数

Examples: gap(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7}

gap(2, 5, 5) --> nil. In C++ {0, 0}. In F# [||]. In Kotlin return[]`

gap(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

([193, 197] is also such a 4-gap primes between 130 and 200 but it's not the first pair)

gap(6,100,110) --> nil or {0, 0} : between 100 and 110 we have 101, 103, 107, 109 but 101-107is not a 6-gap because there is 103in between and 103-109is not a 6-gap because there is 107in between.

如：gap(4,130,200)，在[130,200]这个区间内，gap为4的素数为[163,167]

埃氏筛法

由于2是最小的素数，将所有2的倍数置位，它们不可能是素数辽
接下来最小的素数是3，再将所有3的倍数置位，它们不可能是素数辽
由于4被置位，所以跳过
接下来的数字是5，将所有5的倍数置位，它们不可能是素数辽
......
最容易想到的找素数算法，是用除的方法，埃氏筛法是用找倍数的方法，反向思维，妙啊

a = []
for i in range (0,n):
    a.append(1)
    a[0] = 0
    a[1] = 0
    for i in range (2,n):
        if(a[i]):
            for j in range(2*i,n,i):
                a[j] = 0

在这之后再找gap与给定值一致的素数就容易多了

后续

用这个方法提交的时候提示timeout，呜呜，由于测试的数据量太大，使用list存储素数的话就会timeout。看了下自己的程序，好多步骤属于多余步骤QAQ

solution

def gap(g, m, n):
    prev = None
    for i in range(m if m%2 else m+1, n+1, 2):
        isPrime = True
        for k in range(2, round(i**0.5)+1):
            if i%k == 0:
                isPrime = False
                break
        if isPrime:
            if prev:
                if i-prev == g:
                    return [prev, i]
            prev = i
    return None

后续

做题的时候顺便查了一下米勒-罗宾素性测试，以下公式来源于
https://blog.csdn.net/zxc001vbnm/article/details/47981673

image.png
自己在纸上简单证明了一下，找到了大学时期的那种感觉ovo