Created
March 13, 2021 13:35
-
-
Save lahdjirayhan/f1221c5a68b35c0b8b9763f70e39d736 to your computer and use it in GitHub Desktop.
Finding prime numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"metadata": { | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.8.5-final" | |
}, | |
"orig_nbformat": 2, | |
"kernelspec": { | |
"name": "python3", | |
"display_name": "Python 3.8.5 64-bit (conda)", | |
"metadata": { | |
"interpreter": { | |
"hash": "95f73c80f2cbaf255d7027b59e7d5ad292e842b9f06b36832043f6106b2d029c" | |
} | |
} | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2, | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"import numpy as np" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def indivisible(x, primes):\n", | |
" for prime in primes:\n", | |
" if x % prime == 0:\n", | |
" return False\n", | |
" return True\n", | |
"\n", | |
"def naive_sieve(n):\n", | |
" \"\"\"This is widely known as trial division.\"\"\"\n", | |
" primes = [2]\n", | |
" for number in range(2, n+1):\n", | |
" if indivisible(number, primes):\n", | |
" primes.append(number)\n", | |
" return primes\n", | |
"\n", | |
"def squared_sieve(n):\n", | |
" largest_square_ = int(np.ceil(np.sqrt(n)))\n", | |
" primes = naive_sieve(largest_square_)\n", | |
" candidate_primes = [i for i in range(1, n+1)]\n", | |
" for prime in primes:\n", | |
" m = prime-1\n", | |
" while m < n:\n", | |
" candidate_primes[m] = None\n", | |
" m += prime\n", | |
" \n", | |
" primes.extend([prime for prime in candidate_primes if prime is not None][1:])\n", | |
" return primes\n", | |
"\n", | |
"def doubly_squared_sieve(n):\n", | |
" largest_square_ = int(np.ceil(np.sqrt(n)))\n", | |
" primes = squared_sieve(largest_square_)\n", | |
" candidate_primes = [i for i in range(1, n+1)]\n", | |
" for prime in primes:\n", | |
" m = prime-1\n", | |
" while m < n:\n", | |
" candidate_primes[m] = None\n", | |
" m += prime\n", | |
" \n", | |
" primes.extend([prime for prime in candidate_primes if prime is not None][1:])\n", | |
" return primes" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"16.3 s ± 3.39 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%%timeit\n", | |
"naive_sieve(100_000)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 6, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"138 ms ± 22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%%timeit\n", | |
"squared_sieve(100_000)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 7, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"126 ms ± 4.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%%timeit\n", | |
"doubly_squared_sieve(100_000)" | |
] | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment