luogu-dev / cyaron

CYaRon: Yet Another Random Olympic-iNformatics test data generator
GNU Lesser General Public License v3.0
1.35k stars 168 forks source link

math.py 的筛质数有问题 #22

Closed ghost closed 6 years ago

ghost commented 7 years ago

prime_sieve(25) [2, 3, 5, 9, 11, 15, 17, 23]

prime_sieve(20) Traceback (most recent call last): File "", line 1, in File "C:\Program Files\Python36\lib\site-packages\cyaron\math.py", line 258, in prime_sieve sieve[iint(i/2)::i] = [False] (int((n-ii-1)/(2i))+1) ValueError: attempt to assign sequence of size 2 to extended slice of size 3

findegil commented 7 years ago

+1

findegil commented 7 years ago
def p(n):
    k = n//2
    sieve = [True] * k
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,k) if sieve[i]]
gcgeng commented 6 years ago

30

Is it solved?