# Code sample


```python
def primes(n):
    if n==2:
        return [2]
    elif n<2:
        return []

    s=range(3,n+1,2)
    mroot = n ** 0.5
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)/2
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    x = [2]
    for y in s:
        if y:
            x.append(y)
    return x
```


```python
print(primes(100))
```

## Python version


```python
def primes1(n):
    if n==2:
        return [2]
    elif n<2:
        return []

    s=[i for i in range(3,n+1,2)]  # python 3 syntax
    mroot = n ** 0.5
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)//2  # python 3 syntax
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    x = [2]
    for y in s:
        if y:
            x.append(y)
    return x
```


```python
print(primes1(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


## Library function and dot operation


```python
from math import sqrt  # import the function

def primes2(n):
    if n==2:
        return [2]
    elif n<2:
        return []

    s=[i for i in range(3,n+1,2)]
    mroot = sqrt(n)  # add the library function
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)//2
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    x = [2]
    for y in s:
        if y:
            x.append(y)
    return x
```


```python
print(primes2(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


## List Comprehension


```python
from math import sqrt

def primes3(n):
    if n==2:
        return [2]
    elif n<2:
        return []

    s=[i for i in range(3,n+1,2)]  # list comprehension syntax
    mroot = sqrt(n)
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)//2
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    return [2] + [x for x in s if x]  # list comprehension syntax
```


```python
print(primes3(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


## Data Structure


```python
from numpy import arange
from math import sqrt

def primes4(n):
    if n==2:
        return [2]
    elif n<2:
        return []

    s=arange(3,n+1,2)  # numpy array
    mroot = sqrt(n)
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)//2
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    return [2] + [x for x in s if x]
```


```python
print(primes4(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


# Benchmarking

### Creating a benchmarking function


```python
from time import time

def benchmarking(function, n_repeat):
    ti = time()
    for _ in range (n_repeat):
        function
        
    return (time() - ti)
```


```python
print(benchmarking(primes1(100), 100000000))  # using python 3
```

    1.99668288230896



```python
print(benchmarking(primes2(100), 100000000))  # using library function
```

    1.9916484355926514



```python
print(benchmarking(primes3(100), 100000000))  # using list comprehension syntax
```

    1.9629108905792236



```python
print(benchmarking(primes4(100), 100000000))  # using numpy array
```

    1.9116380214691162


### Module: [timeit](https://docs.python.org/3/library/timeit.html)

Using IPython magic commands


```python
%timeit primes1(100)  # using python 3
```

    5.03 µs ± 57.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%timeit primes2(100)  # using library function
```

    4.94 µs ± 26.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%timeit primes3(100)  # using list comprehension syntax
```

    4.45 µs ± 56.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%timeit primes4(100)  # using numpy array
```

    9.46 µs ± 485 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)


# CPU profiling

Using IPython magic commands


```python
%load_ext line_profiler
```


```python
%lprun -f primes1 primes1(100)  # using python 3
```


```python
%lprun -f primes4 primes4(100)  # using numpy array
```

## Improving the code?

From here it is an iterative process. 


```python
from math import sqrt

def primes5(n):
    if n==2:
        return [2]
    elif n<2:
        return []

    s=list(range(3,n+1,2))  # list
    mroot = sqrt(n)
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)//2
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    return [2] + [x for x in s if x]
```


```python
print(primes5(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]



```python
%timeit primes5(100)  # using library function
```

    4.05 µs ± 89.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)


# Native-speed code

* [Numba](http://numba.pydata.org/)
* [Cython](https://cython.org/)
* [F2PY](https://numpy.org/doc/stable/f2py/)

## Numba


```python
from math import sqrt
from numba import jit

@jit
def primes6(n):
    if n==2:
        return [2]
    elif n<2:
        return [0]  # all returns need have the same tipe. Zero is not rigth!

    s=list(range(3,n+1,2))  # list
    mroot = sqrt(n)
    half=(n+1)//2-1
    i=0
    m=3

    while m <= mroot:
        if s[i]:
            j=(m*m-3)//2
            s[j]=0
        while j<half:
            s[j]=0
            j+=m
        i=i+1
        m=2*i+3
    return [2] + [x for x in s if x]
```


```python
print(primes6(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]



```python
%timeit primes6(100)  # using library function
```

    982 ns ± 20.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)


# Parallel running

[Multiprocessing](https://docs.python.org/3/library/multiprocessing.html)


```python
from sympy import isprime 

def prime(i):
    if (isprime(i)):
        return(i)
```


```python
from multiprocessing import Pool

def multi_primes(N):
    pool = Pool(processes=8)
    input_number = [i for i in range(N)]
    x = pool.map(prime, input_number)
    return [i for i in x if i!=None]
```


```python
print(multi_primes(100))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]



```python
benchmarking(multi_primes(5000000),1)
```




    2.1457672119140625e-06




```python
benchmarking(primes6(5000000),1)
```




    2.384185791015625e-06



fd2298528b784a4bcb2b68ddb939ffdd8e5222c4
ipynb
Jupyter Notebook
3-speed_up/speed-up.ipynb
patricia-ternes/LIDA-python-workshop
320b63d935b1eefdbdf260dc29d3708a94b28dd7
MIT
3-speed_up/speed-up.ipynb
patricia-ternes/LIDA-python-workshop
320b63d935b1eefdbdf260dc29d3708a94b28dd7
MIT
3-speed_up/speed-up.ipynb
patricia-ternes/LIDA-python-workshop
320b63d935b1eefdbdf260dc29d3708a94b28dd7
MIT
Qwen/Qwen-72B
1. YES
2. YES