Skip to content

Instantly share code, notes, and snippets.

@genkuroki

genkuroki/num_primes.ipynb

Created May 30, 2021 13:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save genkuroki/5cb3d726058fd746945200614e518b61 to your computer and use it in GitHub Desktop.
Save genkuroki/5cb3d726058fd746945200614e518b61 to your computer and use it in GitHub Desktop.
Download ZIP
num_primes
Display the source blob
Display the rendered blob
Raw
num_primes.ipynb
{
"cells": [
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "versioninfo()",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": "Julia Version 1.7.0-DEV.1129\nCommit 9117b4d6d6 (2021-05-20 16:42 UTC)\nPlatform Info:\n OS: Windows (x86_64-w64-mingw32)\n CPU: Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz\n WORD_SIZE: 64\n LIBM: libopenlibm\n LLVM: libLLVM-11.0.1 (ORCJIT, skylake)\nEnvironment:\n JULIA_NUM_THREADS = 12\n JULIA_PYTHONCALL_EXE = C:\\Users\\genkuroki\\.julia\\conda\\3\\python.exe\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "https://twitter.com/mat_der_d/status/1398929529364643841"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "https://smooth-pudding.hatenablog.com/entry/2020/08/29/183949"
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "module A\n\nfunction is_prime(num)\n if num <= 1\n return false\n end\n div = (num % i == 0 for i = 2:num-1)\n return !(true in div)\nend\n\nfunction num_primes(maxnum)\n primes = [n for n = 1:maxnum if is_prime(n)]\n return length(primes)\nend\n\nend",
"execution_count": 2,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 2,
"data": {
"text/plain": "Main.A"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "https://smooth-pudding.hatenablog.com/entry/2021/05/30/180849\n\nRust version:\n\n```Rust\nfn main() {\n println!(\"{}\", num_primes(&100000));\n}\n\nfn is_prime(num: &u32) -> bool {\n if num <= &1 {return false};\n for i in 2..*num {\n if num % i == 0 {\n return false;\n }\n }\n return true;\n}\n\nfn num_primes(maxnum: &u32) -> u32 {\n let mut count = 0;\n for i in 1..=*maxnum {\n if is_prime(&i) {count += 1;}\n };\n return count;\n}\n```"
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "module B\n\nfunction is_prime(num)\n if num ≤ 1 return false end\n for i in oftype(num, 2):num-one(num)\n if iszero(num % i)\n return false\n end\n end\n return true\nend\n\nnum_primes(maxnum) = count(is_prime, one(maxnum):maxnum)\n\nend",
"execution_count": 3,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 3,
"data": {
"text/plain": "Main.B"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "module C\n\nrem_int(x::T, y::T) where T<:Signed = Base.srem_int(x, y)\nrem_int(x::T, y::T) where T<:Unsigned = Base.urem_int(x, y)\n\nfunction is_prime(num)\n if num ≤ 1 return false end\n for i in oftype(num, 2):num-one(num)\n if iszero(rem_int(num, i))\n return false\n end\n end\n return true\nend\n\nnum_primes(maxnum) = count(is_prime, one(maxnum):maxnum)\n\nend",
"execution_count": 4,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 4,
"data": {
"text/plain": "Main.C"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "using BenchmarkHistograms",
"execution_count": 5,
"outputs": []
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "@benchmark A.num_primes(100000) seconds=30",
"execution_count": 6,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 6,
"data": {
"text/plain": "samples: 28; evals/sample: 1; memory estimate: 256.72 KiB; allocs estimate: 15\nns\n\n (1.086e9 - 1.091e9] \u001b[32m████████████████████████ \u001b[39m8\n (1.091e9 - 1.095e9] \u001b[32m████████████ \u001b[39m4\n (1.095e9 - 1.1e9 ] \u001b[32m███ \u001b[39m1\n (1.1e9 - 1.105e9] \u001b[32m██████ \u001b[39m2\n (1.105e9 - 1.109e9] \u001b[32m██████████████████████████████ \u001b[39m10\n (1.109e9 - 1.114e9] \u001b[32m█████████ \u001b[39m3\n\n Counts\n\nmin: 1.086 s (0.00% GC); mean: 1.100 s (0.00% GC); median: 1.103 s (0.00% GC); max: 1.114 s (0.00% GC)."
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "@benchmark B.num_primes(100000) seconds=30",
"execution_count": 7,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 7,
"data": {
"text/plain": "samples: 29; evals/sample: 1; memory estimate: 0 bytes; allocs estimate: 0\nns\n\n (1.043e9 - 1.047e9] \u001b[32m███████▌\u001b[39m2\n (1.047e9 - 1.052e9] \u001b[32m██████████████████████████▎\u001b[39m7\n (1.052e9 - 1.057e9] \u001b[32m██████████████████████████████ \u001b[39m8\n (1.057e9 - 1.062e9] \u001b[32m██████████████████████▌\u001b[39m6\n (1.062e9 - 1.066e9] \u001b[32m███████████████ \u001b[39m4\n (1.066e9 - 1.071e9] \u001b[32m███████▌\u001b[39m2\n\n Counts\n\nmin: 1.043 s (0.00% GC); mean: 1.056 s (0.00% GC); median: 1.056 s (0.00% GC); max: 1.071 s (0.00% GC)."
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "@benchmark C.num_primes(100000) seconds=30",
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 8,
"data": {
"text/plain": "samples: 35; evals/sample: 1; memory estimate: 0 bytes; allocs estimate: 0\nns\n\n (8.66e8 - 8.71e8] \u001b[32m██████████████████████████▎\u001b[39m7\n (8.71e8 - 8.76e8] \u001b[32m██████████████████▊\u001b[39m5\n (8.76e8 - 8.8e8 ] \u001b[32m██████████████████████████████ \u001b[39m8\n (8.8e8 - 8.85e8] \u001b[32m██████████████████████████▎\u001b[39m7\n (8.85e8 - 8.89e8] \u001b[32m███████████████ \u001b[39m4\n (8.89e8 - 8.94e8] \u001b[32m███████████▎\u001b[39m3\n (8.94e8 - 8.99e8] \u001b[32m███▊\u001b[39m1\n\n Counts\n\nmin: 866.414 ms (0.00% GC); mean: 878.994 ms (0.00% GC); median: 878.092 ms (0.00% GC); max: 898.586 ms (0.00% GC)."
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "1.086/0.866",
"execution_count": 9,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 9,
"data": {
"text/plain": "1.2540415704387993"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "@time A.num_primes(10^6)",
"execution_count": 10,
"outputs": [
{
"output_type": "stream",
"text": " 91.498245 seconds (18 allocations: 2.001 MiB)\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 10,
"data": {
"text/plain": "78498"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "@time B.num_primes(10^6)",
"execution_count": 11,
"outputs": [
{
"output_type": "stream",
"text": " 82.322474 seconds\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 11,
"data": {
"text/plain": "78498"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "@time C.num_primes(10^6)",
"execution_count": 12,
"outputs": [
{
"output_type": "stream",
"text": " 69.557197 seconds\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 12,
"data": {
"text/plain": "78498"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "91.5/69.6",
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 13,
"data": {
"text/plain": "1.3146551724137931"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"@webio": {
"lastKernelId": null,
"lastCommId": null
},
"kernelspec": {
"name": "julia-1.7-depwarn-o3",
"display_name": "Julia 1.7.0-DEV depwarn -O3",
"language": "julia"
},
"language_info": {
"file_extension": ".jl",
"name": "julia",
"mimetype": "application/julia",
"version": "1.7.0"
},
"toc": {
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"base_numbering": 1,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
},
"gist": {
"id": "5cb3d726058fd746945200614e518b61",
"data": {
"description": "num_primes",
"public": true
}
},
"_draft": {
"nbviewer_url": "https://gist.github.com/5cb3d726058fd746945200614e518b61"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment