### Get all primes up to a given number

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.

all tests pass within the 12000ms time limit.

Hash out 300M test before running.

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 = 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  + list( 2* np.nonzero(bpr) +1) #values from bool indices,modify,listify``````
•  1 1 ```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 = False ``` 5 + ``` v = 1 + int(n**0.5) #limit ``` 6 6 ``` for i in range(3, v, 2): ``` 7 − ``` if bpr[i]: ``` 8 − ``` bpr[i*i::i+i] = 0 ``` 9 − ``` return list(np.nonzero(bpr)) ``` 7 + ``` if bpr[i>>1]: # >>1 equivalent to //2 ``` 8 + ``` bpr[(i*i)>>1::i] = False #"broadcasts" value into slice ``` 9 + ``` return  + list( 2* np.nonzero(bpr) +1) #values from bool indices,modify,listify ```

### Get all primes up to a given number

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))``````
•  1 + ```import numpy as np ``` 1 1 ```def get_primes(n): ``` 2 − ``` bpr = [0,1] * ((n+1)//2) +  * (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): ``` 5 5 ``` if bpr[i]: ``` 6 − ``` ipi, isq = i*2, i*i ``` 7 − ``` bpr[isq::ipi] =  * (( n - isq)//ipi + 1) ``` 8 − ``` return  + [i for i in range(3,n,2) if bpr[i]] ``` 8 + ``` bpr[i*i::i+i] = 0 ``` 9 + ``` return list(np.nonzero(bpr)) ```

### Get all primes up to a given number

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) +  * (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] =  * (( n - isq)//ipi + 1)
return  + [i for i in range(3,n,2) if bpr[i]]``````
•  1 1 ```def get_primes(n): ``` 2 2 ``` bpr = [0,1] * ((n+1)//2) +  * (1 - (1 * 1&n)) ``` 3 3 ``` bpr[:3] = [0, 0, 1] ``` 4 4 ``` for i in range(3, 1+ int(n**0.5), 2): ``` 5 5 ``` if bpr[i]: ``` 6 6 ``` ipi, isq = i*2, i*i ``` 7 7 ``` bpr[isq::ipi] =  * (( n - isq)//ipi + 1) ``` 8 − ``` return [i for i, x in enumerate(bpr) if x] ``` 9 − ``` ``` 8 + ``` return  + [i for i in range(3,n,2) if bpr[i]] ```

### List of divisors of number

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]``````
•  1 1 ```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] ```

### Get all primes up to a given number

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 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) +  * (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] =  * (( n - isq)//ipi + 1)
return [i for i, x  in enumerate(bpr) if x]
``````
•  1 − ```def get_primes(n): ``` 2 − ``` a =  * n ``` 3 − ``` a = a = 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] =  * (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) +  * (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] =  * (( n - isq)//ipi + 1) ``` 8 + ``` return [i for i, x in enumerate(bpr) if x] ``` 9 + ``` ```