Earn extra honor and gain new allies!
Honor is earned for each new codewarrior who joins.
Learn more
Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays

Numpy but with half length array without Even numbers and array turned to boolean, and bitshifting >>1 instead of integer division //2 (not that it seems to make any real difference). All tests execute about 600-700ms quicker than the previous full array.

Added 300,000,000 test:
all tests pass within the 12000ms time limit.

Added 400,000,000 test:
Hash out 300M test before running.

Added 650,000,000 test:
Hash out all other tests prior to running!!!
Test may complete within the time limit if you are lucky!

solved the n = prime issue I was having added a test to make sure that if n is prime it's actually included.

Code
Diff
  • import numpy as np
    def get_primes(n):  
        bpr = np.ones((n+1)//2,dtype=bool) #length (n+1)//2 array of boolean True values
        bpr[0] = False 
        v = 1 + int(n**0.5) #limit
        for i in range(3, v, 2):
            if bpr[i>>1]: # >>1 equivalent to //2
                bpr[(i*i)>>1::i] = False #"broadcasts" value into slice
        return [2] + list( 2* np.nonzero(bpr)[0] +1) #values from bool indices,modify,listify
  • 11
    import numpy as np
    
    2
    def get_primes(n):    
    
    3
        bpr = np.ones(n)
    
    4
        bpr[:2] = bpr[4::2] = 0
    
    5
        v = 1 + int(n**0.5)
    
    2+
    def get_primes(n):  
    
    3+
        bpr = np.ones((n+1)//2,dtype=bool) #length (n+1)//2 array of boolean True values
    
    4+
        bpr[0] = False 
    
    5+
        v = 1 + int(n**0.5) #limit
    
    66
        for i in range(3, v, 2):
    
    7
            if bpr[i]:
    
    8
                bpr[i*i::i+i] = 0 
    
    9
        return list(np.nonzero(bpr)[0])
    
    7+
            if bpr[i>>1]: # >>1 equivalent to //2
    
    8+
                bpr[(i*i)>>1::i] = False #"broadcasts" value into slice
    
    9+
        return [2] + list( 2* np.nonzero(bpr)[0] +1) #values from bool indices,modify,listify
    
Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays

Added a numpy array, saves 2000ms, don't know much about numpy so likely can be bettered
the list conversion seems costly.

Code
Diff
  • import numpy as np
    def get_primes(n):    
        bpr = np.ones(n)
        bpr[:2] = bpr[4::2] = 0
        v = 1 + int(n**0.5)
        for i in range(3, v, 2):
            if bpr[i]:
                bpr[i*i::i+i] = 0 
        return list(np.nonzero(bpr)[0])
  • 1+
    import numpy as np
    
    11
    def get_primes(n):    
    
    2
        bpr = [0,1] * ((n+1)//2) + [0] * (1 - (1 * 1&n))
    
    3
        bpr[:3] = [0, 0, 1]
    
    4
        for i in range(3, 1+ int(n**0.5), 2):
    
    3+
        bpr = np.ones(n)
    
    4+
        bpr[:2] = bpr[4::2] = 0
    
    5+
        v = 1 + int(n**0.5)
    
    6+
        for i in range(3, v, 2):
    
    55
            if bpr[i]:
    
    6
                ipi, isq = i*2, i*i
    
    7
                bpr[isq::ipi] = [0] * (( n - isq)//ipi + 1)
    
    8
        return [2] + [i for i in range(3,n,2) if bpr[i]]
    
    8+
                bpr[i*i::i+i] = 0 
    
    9+
        return list(np.nonzero(bpr)[0])
    
Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays

How did I miss this?

Code
Diff
  • def get_primes(n):    
        bpr = [0,1] * ((n+1)//2) + [0] * (1 - (1 * 1&n))
        bpr[:3] = [0, 0, 1]
        for i in range(3, 1+ int(n**0.5), 2):
            if bpr[i]:
                ipi, isq = i*2, i*i
                bpr[isq::ipi] = [0] * (( n - isq)//ipi + 1)
        return [2] + [i for i in range(3,n,2) if bpr[i]]
  • 11
    def get_primes(n):    
    
    22
        bpr = [0,1] * ((n+1)//2) + [0] * (1 - (1 * 1&n))
    
    33
        bpr[:3] = [0, 0, 1]
    
    44
        for i in range(3, 1+ int(n**0.5), 2):
    
    55
            if bpr[i]:
    
    66
                ipi, isq = i*2, i*i
    
    77
                bpr[isq::ipi] = [0] * (( n - isq)//ipi + 1)
    
    8
        return [i for i, x  in enumerate(bpr) if x]
    
    9
     
    
    8+
        return [2] + [i for i in range(3,n,2) if bpr[i]]
    
Performance
Arrays

Keeping that second if statement in the for loop seems expensive. I pulled it outside and added a pop.

Code
Diff
  • def divisors(n):
        res, rev, v = [], [], 1+int(n**0.5)
        for i in range(1, v):
            x,r = divmod(n, i)
            if not r:
                res.append(i)
                rev.append(x)
        if res[-1] == rev[-1]: 
            rev.pop()
        return res + rev[::-1]
  • 11
    def divisors(n):
    
    2
        res,rev,h=[],[],int(n**.5)
    
    3
        for d in range(1,h+1):
    
    4
            x,r = divmod(n,d)
    
    5
            if not r: 
    
    6
                res.append(d)
    
    7
                if x!=d: rev.append(x)
    
    8
        return res+rev[::-1]
    
    2+
        res, rev, v = [], [], 1+int(n**0.5)
    
    3+
        for i in range(1, v):
    
    4+
            x,r = divmod(n, i)
    
    5+
            if not r:
    
    6+
                res.append(i)
    
    7+
                rev.append(x)
    
    8+
        if res[-1] == rev[-1]: 
    
    9+
            rev.pop()
    
    10+
        return res + rev[::-1]
    
Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays

Not really done this Kumite thing before, I wrote this version of the sieve of erastothenes last year some time, it's pretty fast, though perhaps you can make it faster?

It's fairly straightforward at heart.
Takes a little longer initially but avoids repeatedly iterating over all the multiples of 2, dumps a calculated number of [0]s into the multiples starting from the square of the current number.
I tested it against a few different variants with the time module. I'd love to see how it can get faster.

Code
Diff
  • def get_primes(n):    
        bpr = [0,1] * ((n+1)//2) + [0] * (1 - (1 * 1&n))
        bpr[:3] = [0, 0, 1]
        for i in range(3, 1+ int(n**0.5), 2):
            if bpr[i]:
                ipi, isq = i*2, i*i
                bpr[isq::ipi] = [0] * (( n - isq)//ipi + 1)
        return [i for i, x  in enumerate(bpr) if x]
     
  • 1
    def get_primes(n):
    
    2
        a = [1] * n
    
    3
        a[0] = a[1] = 0
    
    4
        for i in range(2, n):
    
    5
            if a[i]:
    
    6
                x, y = divmod(n - i**2, i)
    
    7
                a[i**2:n:i] = [0] * (x + bool(y))
    
    8
        return [i for i, x in enumerate(a) if x]
    
    1+
    def get_primes(n):    
    
    2+
        bpr = [0,1] * ((n+1)//2) + [0] * (1 - (1 * 1&n))
    
    3+
        bpr[:3] = [0, 0, 1]
    
    4+
        for i in range(3, 1+ int(n**0.5), 2):
    
    5+
            if bpr[i]:
    
    6+
                ipi, isq = i*2, i*i
    
    7+
                bpr[isq::ipi] = [0] * (( n - isq)//ipi + 1)
    
    8+
        return [i for i, x  in enumerate(bpr) if x]
    
    9+