num_primes

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
}