Ad
blinker345678vs.blinker345678

Get all primes up to a given number

Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays
Data Types

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
    • import numpy as np
    • def get_primes(n):
    • bpr = np.ones(n)
    • bpr[:2] = bpr[4::2] = 0
    • v = 1 + int(n**0.5)
    • 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]:
    • bpr[i*i::i+i] = 0
    • return list(np.nonzero(bpr)[0])
    • 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
blinker345678vs.blinker345678

Get all primes up to a given number

Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays
Data Types

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])
    • import numpy as np
    • 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):
    • 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]:
    • 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]]
    • bpr[i*i::i+i] = 0
    • return list(np.nonzero(bpr)[0])
blinker345678vs.blinker345678

Get all primes up to a given number

Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays
Data Types

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]]
    • 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]
    • return [2] + [i for i in range(3,n,2) if bpr[i]]
blinker345678vs.Blind4Basics

List of divisors of number

Performance
Arrays
Data Types

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]
    • def divisors(n):
    • res,rev,h=[],[],int(n**.5)
    • for d in range(1,h+1):
    • x,r = divmod(n,d)
    • if not r:
    • res.append(d)
    • if x!=d: rev.append(x)
    • return res+rev[::-1]
    • 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]
blinker345678vs.FArekkusu

Get all primes up to a given number

Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays
Data Types

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]
    • def get_primes(n):
    • a = [1] * n
    • a[0] = a[1] = 0
    • for i in range(2, n):
    • if a[i]:
    • x, y = divmod(n - i**2, i)
    • a[i**2:n:i] = [0] * (x + bool(y))
    • return [i for i, x in enumerate(a) if x]
    • 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]