{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Prime Number Theorem\n", "\n", "$\\pi(n) = $ the number of prime numbers $\\leq n$. The Prime Number Theorem states that $\\pi(n) \\approx \\frac{n}{\\ln(n)}$. In the following we consider all primes $\\leq 1.000.000$. First we computer a bitvector 'prime' such that prime[p] is true if and only p is a prime number." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "prime = [True] * 1000001\n", "for p in range(2, 1000001):\n", " for f in range(2 * p, 1000001, p):\n", " prime[f] = False" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We next compute select all the prime numbers in the range 2..100, i.e. idx where prime[idx] = True." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "primes = [p for p in range(2, 1000001) if prime[p]]" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "primes[:10]" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import math" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZIAAAD8CAYAAABdCyJkAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzt3XmYVNW19/HvshUcogKKBhkEFY2Ya1RaoWP0thNTTPAmalAT0HAvjokxcQAnjKggQY0oDiSi4AQ4QlREgqBGG6VxQlRCRxEaiJAXnJVxvX/s3VpCD9XdVV3T7/M89VTVrl3n7EMhy7PXHszdERERaaitMt0AERHJbQokIiLSKAokIiLSKAokIiLSKAokIiLSKAokIiLSKAokIiLSKEkFEjO7wMwWmNlbZvagmW1rZp3M7GUzW2Rmk8ysWazbPL6viJ93TDjOkFi+0Mx6JpT3imUVZjY41RcpIiLpU2cgMbO2wG+BYnf/PlAE9AOuB25y987AGmBg/MpAYI277wPcFOthZl3i9w4AegG3mVmRmRUBY4DeQBfglFhXRERywNb1qLedma0HtgdWAEcDp8bPxwNXAbcDfeNrgIeBW83MYvlEd18LvG9mFcBhsV6Fu78HYGYTY923a2vQrrvu6h07dkyy+SIiMm/evP+4e+tUH7fOQOLuy8xsFLAE+BJ4BpgHfOTuG2K1SqBtfN0WWBq/u8HMPgZ2ieVzEg6d+J2lm5V3q6tdHTt2pLy8vK5qIiISmdkH6ThuMl1bLQl3CJ2APYAdCN1Qm6tatMtq+Ky+5dW1ZZCZlZtZ+apVq+pquoiINIFkku3HAu+7+yp3Xw88CvwQaGFmVXc07YDl8XUl0B4gfr4zsDqxfLPv1FS+BXcf6+7F7l7cunXK785ERKQBkgkkS4DuZrZ9zHUcQ8hfzAJOjHUGAFPi66nxPfHzZz0sMTwV6BdHdXUCOgOvAHOBznEUWDNCQn5q4y9NRESaQjI5kpfN7GHgVWAD8BowFngSmGhm18Syu+JX7gLujcn01YTAgLsvMLPJhCC0ATjX3TcCmNl5wHTCiLBx7r4gdZcoIiLpZLm6H0lxcbEr2S4ikjwzm+fuxak+rma2i4hIoyiQiIjkiLKlZQx/YThlS8sy3ZRvSXZCooiIZFDZ0jKOmXAM6zauo1lRM2b2n0lJ+5JMNwvQHYmISE6YvXg26zauY6NvZN3GdcxePDvTTfqaAomISA4o7VhKs6JmFFkRzYqaUdqxNNNN+pq6tkREckBJ+xJm9p/J7MWzKe1YmjXdWqBAIiKSNcqWltUaKEral2RVAKmiQCIikgWyOZleF+VIRESyQDYn0+uiQCIikgWyOZleF3VtiYhkgWxOptdFgUREpAnVllDP1mR6XRRIRESaSC4n1GujHImISBPJ5YR6bRRIRESaSC4n1Gujri0RkRSqKweSqwn12iiQiIikSDI5kFxNqNemzq4tM9vPzF5PeHxiZr8zs1ZmNsPMFsXnlrG+mdloM6swszfN7JCEYw2I9ReZ2YCE8q5mNj9+Z3TcG15EJKekPQfiDqtWpfaYKVBnIHH3he5+kLsfBHQFvgAeAwYDM929MzAzvgfoDXSOj0HA7QBm1goYCnQDDgOGVgWfWGdQwvd6peTqRESaUFpzIK+/DscdB4cfDuvXp+64KVDfZPsxwL/c/QOgLzA+lo8HToiv+wITPJgDtDCzNkBPYIa7r3b3NcAMoFf8bCd3L/OwgfyEhGOJiOSMqhzIsKOGpW5ob2UlnHEGHHIIvPYanHde44+ZYvXNkfQDHoyvd3f3FQDuvsLMdovlbYGlCd+pjGW1lVdWUy4iknWabIXeTz+FkSPhhhtg40a48EK49FJo0aLxx06xpAOJmTUDfgoMqatqNWXegPLq2jCI0AVGhw4d6miGiEhqNcmEwg0b4K674MorYeVK6NcPhg+Hjh1Te54Uqk/XVm/gVXf/ML7/MHZLEZ9XxvJKoH3C99oBy+sob1dN+Rbcfay7F7t7cevWrevRdBGRxktrMt0dnnoKfvADOOss2HdfmDMHHnwwq4MI1C+QnMI33VoAU4GqkVcDgCkJ5f3j6K3uwMexC2w60MPMWsYkew9gevzsUzPrHkdr9U84lohI1khbMr0qkf7jH8O6dfDoo/D889CtW2qOn2ZJdW2Z2fbAccCZCcUjgMlmNhBYApwUy58C+gAVhBFeZwC4+2ozGwbMjfWudvfV8fXZwD3AdsC0+BARySopn1C4bBlcfjmMHw8tW8LNN4e7kWbNUtPgJmJhoFTuKS4u9vLy8kw3Q0TyTF3J9JT47LOQSB81KiTSf/tbuOyytCfSzWyeuxen+ria2S4iEqU9mb5xI4wbB1dcAR9+CL/4RUikd+qUunNkgBZtFBGJ0ppMf/ppOOggGDQI9t4byspg4sScDyKgQCIi8rW0JNPnz4eePaF3b/jiC3joIfjHP6B798YfO0uoa0tECkqTrc67YkWYCzJuHOy8M9x4I5xzDjRv3sgryD4KJCJSMJpkdd7PPw+z0UeODEN5f/vbkBNp1aqRrc9e6toSkYKR1hzIxo1wzz1hIuHQodCrF7z9Ntx0U14HEVAgEZECkrYJhc8+C8XFYXHFdu3ghRfg4Ydhn31Sc/wsp64tESkYKZ9Q+M47cPHF8MQTsOee8MADYUjvVoX1/+gKJCKSd+pKqDc6gKxcCVddBWPHwg47wIgRcP75sO22jTtujlIgEZG8ktZJhV99FZYxue66kFQ/88wQUAp8EdnCuv8SkbyXloS6e1iF93vfg8GD4cgjw/yQMWMKPoiAAomI5JmUJ9RfeglKSuDUU8PCijNnwt/+Bvvvn5L25gN1bYlIXklZQv299+CSS8LoqzZtwsTC/v2hqCi1Dc4DCiQiknPSut3tRx/BNdfALbfA1luHHMiFF4akulRLgUREckrakunr18Mdd8Af/wirV8Ppp4eAsscejT92nlOORERySsqT6e4wdSp8//thOZMf/ABefTV0ZSmIJEWBRERySkqT6a+9BsccA337hkmEf/sb/P3vYbl3SVpSgcTMWpjZw2b2rpm9Y2YlZtbKzGaY2aL43DLWNTMbbWYVZvammR2ScJwBsf4iMxuQUN7VzObH74yOe7eLiGyhKpk+7KhhDe/WWrYsLGfStSu8+Sbcemt4Pv540D8/9ZbUVrtmNh54wd3/ambNgO2BS4HV7j7CzAYDLd39EjPrA/yGsG97N+Bmd+9mZq2AcqAYcGAe0NXd15jZK8D5wBzCnu+j3b3Wfdu11a5I/krbdreffw5/+lN4bNgQZqNfemnat7jNFhnbatfMdgKOBE4HcPd1wDoz6wuUxmrjgdnAJUBfYIKHCDUn3s20iXVnuPvqeNwZQC8zmw3s5O5lsXwCcAJQayARkfyUlmT6pk0wYUIIGitWwEknwfXX58XuhNkgma6tvYBVwN1m9pqZ/dXMdgB2d/cVAPF5t1i/LbA04fuVsay28spqyrdgZoPMrNzMyletWpVE00Uk16Q8mT5r1jcr83boAC++CJMnK4ikUDKBZGvgEOB2dz8Y+BwYXEv96joYvQHlWxa6j3X3Yncvbq1lCUTyUsqS6f/8Z0iiH300/L//F5Y4KSuDH/4wpe2V5OaRVAKV7v5yfP8wIZB8aGZt3H1F7LpamVC/fcL32wHLY3npZuWzY3m7auqLSJ5K63a3q1eHuSC33QbbbQfDh4dcyHbbpfAKJFGdgcTd/21mS81sP3dfCBwDvB0fA4AR8XlK/MpU4Dwzm0hItn8cg8104Lqq0V1AD2CIu682s0/NrDvwMtAfuCWF1ygiWSRt292uWxeCx9VXw8cfw6BBIaDstlvd35VGSXZm+2+A++OIrfeAMwjdYpPNbCCwBDgp1n2KMGKrAvgi1iUGjGHA3Fjv6qrEO3A2cA+wHSHJrkS7SJ6qLgfSqGS6O0yZAhddBBUV0LNn2DP9gANS12ipVVKBxN1fJwzb3dwx1dR14NwajjMOGFdNeTnw/WTaIiK5rSoHUnVH0qgJha++Cr//PTz3HHTpAtOmhb3SpUlprS0RaVIpWZ132TK47LIwpHfXXeH22+F//zcssihNTn/qIpJyaVud9/PPYdQoGDkyTCi8+GIYMgR23jkFrZaGUiARkZRK24TC++4LEwqXLYOTTw77pGsuSFbQoo0iklIpn1D4/PNw2GEwYAC0bRsmFE6apCCSRRRIRCSlUjah8F//gp//HP77v+HDD8MdiSYUZiV1bYlISjU6mV61Q+Ho0dCsGQwbFkZmbb99ehosjaZAIiINUtfs9HoHkA0bYOxYGDo0LGlyxhkhoLRpk8JWSzookIhIvaU8oT5tGvzhD/DOO1BaCjfeCAcfnLL2SnopRyIi9ZayhPqCBWECYZ8+Yc/0xx6DZ59VEMkxCiQiUm+NTqivWgXnnAMHHggvvxzuQBYsgBNO0A6FOUhdWyJSbw1OqK9dC7fcEhLon38egslVV8Euu6S1vZJeCiQiUq2Uzk53D91WF18chvX26RNmqO+/f4pbLZmgQCIiW0hpMj1xYcUDDoDp06FHj9Q2WDJKORIR2UJKkukrVsCvfx22uX377bCw4uuvK4jkId2RiMgWGrXU+5dfhv1ARowII7EuvDCs1KuFFfOWAomIbKFByXR3mDgRLrkEli4Ny5uMHAl77ZX+BktGJdW1ZWaLzWy+mb1uZuWxrJWZzTCzRfG5ZSw3MxttZhVm9qaZHZJwnAGx/iIzG5BQ3jUevyJ+V+P/RNKsbGkZw18YTtnSsmo/L2lfwpAjhiQXRObMCWtgnXpq2B/kuefg4YcVRApEfXIkR7n7Qe5etVPiYGCmu3cGZsb3AL2BzvExCLgdQuABhhL2cT8MGJqwf/vtsW7V97TFmUgaVSXTr5h1BcdMOKbGYFKnpUvhtNOgpAQWL4a774bycjjyyJS2V7JbY5LtfYHx8fV44ISE8gkezAFamFkboCcww91Xu/saYAbQK362k7uXxW16JyQcS0TSoNHJ9M8+gyuvhP32g0cfDTmQRYvg9NNhK43hKTTJ5kgceMbMHLjT3ccCu7v7CgB3X2Fmu8W6bYGlCd+tjGW1lVdWUy4iadLgZHrVBlNDhsDy5dCvX0iq77lnWtsr2S3ZQHK4uy+PwWKGmb1bS93q8hvegPItD2w2iNAFRocOHWpvsUiBq2t13non0198EX73u9B1deihMHkyHH54mlovuSSpQOLuy+PzSjN7jJDj+NDM2sS7kTbAyli9Emif8PV2wPJYXrpZ+exY3q6a+tW1YywwFqC4uLjaYCMiyU0oTHpm+gcfhJFYkyaFHQrvvTck1dWFJVGdfxPMbAcz27HqNdADeAuYClSNvBoATImvpwL94+it7sDHsQtsOtDDzFrGJHsPYHr87FMz6x5Ha/VPOJaINEBKJhR+9hlcfnnIg0ydGvYJWbgQfvlLBRH5lmTuSHYHHosjcrcGHnD3p81sLjDZzAYCS4CTYv2ngD5ABfAFcAaAu682s2HA3FjvandfHV+fDdwDbAdMiw8RaaBGTSjctAkmTIBLLw2z0087DYYPh/bt6/6uFCQLA6VyT3FxsZeXl2e6GSJZq65FF6v1wgtwwQUwbx507w5//jN065behkqTMbN5CVM4UkYz20VyVEpX5128OKzM+9BD0K4dPPBAGJGlucGSBAUSkRyUstV5P/00DN+94QYoKoI//jGsjbX99qlvtOQtZcxEclCjk+mbNoVZ6PvuC9ddByedFBLpV16pICL1pjsSkRzUqGT6Cy+E+SCvvhryII8/rjyINIoCiUgOatCEwsWLw3yQyZNDHuT+++GUU5QHkUZTIBHJUilLpn/2WciDjBoV5n9cdRVcdJG6sCRlFEhEslBKkumbNoVZ6EOGhPkgp54aAormg0iKKdkukoUanUx/6aWQ/zj99BA4XnopdGUpiEgaKJCIZKGqZHqRFdUvmb50abjzOPxwWLYszFAvKwv7hYikibq2RLJQvZPpX3wRtrUdOTJseXv55SGx/p3vNE2DpaApkIhkUF1LvdcZQKr2Sb/4YqishJNPDsFE+4NIE1IgEcmQRifUy8vh/PND/uPgg8OyJkcckb4Gi9RAORKRDGlwQn3FipBEP/RQqKiAv/4V5s5VEJGM0R2JSIbUe3b6V1/BTTeFJU3Wrg3dWZddBjvt1CTtFamJAolIhiSdUHcPy5j84Q/w/vvQt2+YXLjPPk3bYJEaKJCIpFGjZ6e/+WZYF2vWLDjgAJgxA449No0tFqk/BRKRNGlUMv0//4ErroCxY6FFCxgzBgYNgq31n6xkn6ST7WZWZGavmdkT8X0nM3vZzBaZ2SQzaxbLm8f3FfHzjgnHGBLLF5pZz4TyXrGswswGp+7yRDKnQcn09evh5puhc2f4y1/gnHNg0aLwrCAiWao+o7bOB95JeH89cJO7dwbWAANj+UBgjbvvA9wU62FmXYB+wAFAL+C2GJyKgDFAb6ALcEqsK5LT6j07ffp0OPDA0JV16KHwxhtwyy3QqlWTtFekoZIKJGbWDvgx8Nf43oCjgYdjlfHACfF13/ie+PkxsX5fYKK7r3X394EK4LD4qHD399x9HTAx1hXJaVXJ9GFHDau9W2vRIvjJT6BXr3BHMmVKCCoHHNC0DRZpoGTvlf8MXAzsGN/vAnzk7hvi+0qgbXzdFlgK4O4bzOzjWL8tMCfhmInfWbpZuXbZkZzQqGT6J5/AsGGhK6t5c7j++jDBsHnzNLdaJLXqDCRmdjyw0t3nmVlpVXE1Vb2Oz2oqr+6uyKspw8wGAYMAOnToUEurRdKvwcn0TZvgnnvC8u4rV4bJhcOHw3e/m+4mi6RFMl1bhwM/NbPFhG6nowl3KC3MrCoQtQOWx9eVQHuA+PnOwOrE8s2+U1P5Ftx9rLsXu3tx69atk2i6SPo0KJn+0ktw2GEwcCDsvTe88krYO11BRHJYnYHE3Ye4ezt370hIlj/r7qcBs4ATY7UBwJT4emp8T/z8WXf3WN4vjurqBHQGXgHmAp3jKLBm8RxTU3J1ImlUr2R6ZSWcdlpY3n3FCrjvPnjxxZBUF8lxjRlPeAkw0cyuAV4D7orldwH3mlkF4U6kH4C7LzCzycDbwAbgXHffCGBm5wHTgSJgnLsvaES7RJpEUjPTv/wSbrwxLGuycWNY0mTwYC3vLnnFws1C7ikuLvby8vJMN0PyXF3J9Bq5w2OPhWVNFi+Gn/8c/vQn6NQpbW0VqYuZzXP34lQfVzOcRGrQ4GT6W2+F0VfPPgvf/z7MnAlHH53+BotkiJaRF6lBvZPpq1fDb34DBx0Er70Gt94anhVEJM/pjkSkBkkv875xY1gT64orYM0aOOssuPpq2GWXJm2vSKYokIjUIKlk+nPPwW9/G1bpLS0NkwsPPLDJ2yqSSQokUtAaPDN9yRK46CKYPBk6dICHHgoJdatu3q1IflMgkYLVoGT6l1+G0VcjRoSRWVddFQLK9ts3SZtFspGS7VKw6pVMd4dHHoH994ehQ+H44+Hdd8NrBREpcAokUrCSnpn+1lthV8ITTwz7o8+aFbq09tyzSdsrkq3UtSUFq85k+po1oetqzJgQQG69Fc48UxtMiWxG/0VI3qstoV5tMn3jRhg3Di69NMwNGTQIrrlGw3lFaqBAInmt3gn1l14Kw3nnzYMjjoDRo8MEQxGpkXIkkteSTqgvXw79+4fVef/9b3jwwTBHREFEpE4KJJLX6kyor10LI0fCfvvBpElhdd6FC6FfP80JEUmSurYkr9WaUJ82LSyuuGgR/PSnYbn3vffOXGNFcpQCieS8es9Or6iACy6AJ56AffcNAaVXryZssUh+USCRnFavZPrnn4cNpkaNgmbNQpfW+eeH1yLSYMqRSE5LKpnuDhMnhjzIddfBL34R8iAXXaQgIpICdQYSM9vWzF4xszfMbIGZ/TGWdzKzl81skZlNivutE/dkn2RmFfHzjgnHGhLLF5pZz4TyXrGswswGp/4yJV/VmUyvWpX3lFNgt93gH/+ACRNgjz0y0VyRvJTMHcla4Gh3/wFwENDLzLoD1wM3uXtnYA0wMNYfCKxx932Am2I9zKwLYf/2A4BewG1mVmRmRcAYoDfQBTgl1hWpU1UyfdhRw77drbVmTdhk6uCDwxInd9wBc+eG4b0iklJ15kg8bOr+WXy7TXw4cDRwaiwfD1wF3A70ja8BHgZuNTOL5RPdfS3wvplVAIfFehXu/h6AmU2Mdd9uzIVJ/qhXMn3TpjArfciQMCv9rLNg2DBo1aqJWy1SOJJKtse7hnnAPoS7h38BH7n7hlilEmgbX7cFlgK4+wYz+xjYJZbPSThs4neWblberd5XInmpXsn0V16B88775s7j1ls1oVCkCSSVbHf3je5+ENCOcBexf3XV4nN1s7i8AeVbMLNBZlZuZuWrVq2qu+GS85JKpq9cCQMHQrduUFkJ990HL7ygICLSROo1asvdPwJmA92BFmZWdUfTDlgeX1cC7QHi5zsDqxPLN/tOTeXVnX+suxe7e3Hr1q3r03TJUbUm0zdsCGth7btvSKBfdFEYjXXaaZqVLtKEkhm11drMWsTX2wHHAu8As4ATY7UBwJT4emp8T/z82ZhnmQr0i6O6OgGdgVeAuUDnOAqsGSEhPzUVFye5r8Zk+vPPwyGHhHkghx0G8+eHeSE77pjZBosUoGRyJG2A8TFPshUw2d2fMLO3gYlmdg3wGnBXrH8XcG9Mpq8mBAbcfYGZTSYk0TcA57r7RgAzOw+YDhQB49x9QcquULJevZLpy5eHO48HHgh7pT/yCPzP/+gORCSDLNws5J7i4mIvLy/PdDOkkZJOpq9bBzffDFdfDevXw8UXw+DB2uZWpB7MbJ67F6f6uJrZLhmVVDL973+HH/wgBI+jjoIFC0JAURARyQoKJJJRtSbTlywJ+6Qfd1y4C3niCZg6VSv0imQZLdooGVXtMu9r18INN8C114Z1soYNgwsvhG23zXRzRaQaCiSSdvVKpj/9dNjqdtGikES/6SbYc88mbrGI1IcCiaRV0sn0xYvDHiGPPx7mhTz9NPTsuWU9Eck6ypFIWtWZTP/qK7jmGth/f3jmGRg+PKzYqyAikjN0RyJpVZVMr7oj+VYyfdq0sELvv/4Vkuo33gjt29d4LBHJTgokklbVJtMTu7H22w9mzIBjj810U0WkgRRIJCVqS6h/nUyv6sa69lrYaisYMSIEFO1SKJLTFEik0ZJKqD/9dOjGqqhQN5ZInlGyXRqt1oT6kiXws59B797hLmT6dHjoIQURkTyiQCKNVu3s9HXrwgis730v3I1ce20YjdWjR6abKyIppq4tabQtEur//AKOOzDsDaJJhSJ5T4FEkpLU7PStOsDvfw+TJ4f1sJ56KnRpiUheUyCROtWZTF+/PuxUeNVV4fVVV8Ell2htLJECoRyJ1KnWZPo//hF2KrzwQjjyyLDE+9ChCiIiBUSBROpUbTJ95Uo44ww44gj45JMwufCJJ7TEu0gBSmbP9vZmNsvM3jGzBWZ2fixvZWYzzGxRfG4Zy83MRptZhZm9aWaHJBxrQKy/yMwGJJR3NbP58TujzbRvajb51r7ppz1DyZNvhBnp990Xdil8+23o21fb3YoUqGRyJBuAP7j7q2a2IzDPzGYApwMz3X2EmQ0GBgOXAL2BzvHRDbgd6GZmrYChQDHg8ThT3X1NrDMImAM8BfQCpqXuMqUuSSXTVzaDk8+GuXOhtBTGjIEuXZq+sSKSVeoMJO6+AlgRX39qZu8AbYG+QGmsNh6YTQgkfYEJHjaDn2NmLcysTaw7w91XA8Rg1MvMZgM7uXtZLJ8AnIACSZOpM5n+0Udw+eVw222w225w//1wyim6AxERoJ45EjPrCBwMvAzsHoNMVbDZLVZrCyxN+FplLKutvLKa8urOP8jMys2sfNWqVfVputSixmS6ewga3/se3H47nHtumBty6qkKIiLytaQDiZl9B3gE+J27f1Jb1WrKvAHlWxa6j3X3Yncvbt26dV1NliRVm0x/992wIu8vfwkdOoTurFtugZ13znRzRSTLJDWPxMy2IQSR+9390Vj8oZm1cfcVsetqZSyvBBIXUmoHLI/lpZuVz47l7aqpL00kcWb60bt3p9sdT8Cf/gTbbx+6swYNgqKiTDdTRLJUMqO2DLgLeMfdb0z4aCpQNfJqADAlobx/HL3VHfg4dn1NB3qYWcs4wqsHMD1+9qmZdY/n6p9wLGkiJe1LGPLJgXTr+Wu47jro1y90Y519toKIiNQqmTuSw4FfAfPN7PVYdikwAphsZgOBJcBJ8bOngD5ABfAFcAaAu682s2HA3Fjv6qrEO3A2cA+wHSHJrkR7itU6KquyEs4/Hx59NGx5O2tWGJUlIpIEC4Orck9xcbGXl5dnuhk5ocZRWRs2hLzHlVeG11dcEWaoa6MpkbxkZvPcvTjVx9VaWwWgulFZJcu3gjPPhDfeCAsrjhkDnTpluqkikoO0REoBSByV1XrdNpzxl7lQUgKrVsHDD8OTTyqIiEiDKZAUgJL2Jcz81d95ZMPP+WDs9nz3/ikhJ/Luu/Dzn2tOiIg0irq28kStyfSKCkrOHgp//zsceihMvxMOPjgzDRWRvKNAkgdqTKavWwcjR8I110Dz5nDrrXDWWRrOKyIppUCSB6pNpi/eEJLp77wDJ58ctrvdY49MN1VE8pByJHkgMZn+3bXb8OvbysImU19+Gba7nTRJQURE0kaBJA9UJdMfW/cz3r9jW3Z/6Kmw1e2CBdozXUTSTl1bOaTGhHpFBSVnXQkzZ0L37nDnnXDggZlrqIgUFAWSHFFtQn33rjBqFAwbFmaj33ZbyItspRtNEWk6CiQ5YvOE+qInJlBy2yB46y048US4+WblQUQkIxRIckRVQn3bz9cyYib8au6d0K4dTJ0KP/lJppsnIgVMfSA5oqRdd17b9XI+GLsD/1fu2Pnnw9tvK4iISMbpjiQXLFsG557LflOmwEEHwdN/geKUL+ApItIguiPJImVLyxj+wnDKlpaFgk2bwl7pXbrAM8+EWepz5yqIiEhW0R1Jlth8VNZLJXdx0JVj4MUXw97pd9wBe++d6Wa5JQhhAAALE0lEQVSKiGwhma12x5nZSjN7K6GslZnNMLNF8bllLDczG21mFWb2ppkdkvCdAbH+IjMbkFDe1czmx++MjtvtFpyqUVlbrd/IxTO/4vu9fhVyIPfcE+5GFEREJEsl07V1D9Brs7LBwEx37wzMjO8BegOd42MQcDuEwAMMBboBhwFDq4JPrDMo4Xubn6sglHYs5UfLinh1LFw1y/moz9FhmfcBA7TMu4hktToDibs/D6zerLgvMD6+Hg+ckFA+wYM5QAszawP0BGa4+2p3XwPMAHrFz3Zy9zIPe/5OSDhW4fjsM0pGTWTWX9bTnp15555R7Pr4M7DbbplumYhInRqaI9nd3VcAuPsKM6v6F68tsDShXmUsq628spryvFTtEifPPAODBsGSJdi557Lzddex8447ZrahIiL1kOpke3V9MN6A8uoPbjaI0A1Ghw4dGtK+jNk8mf7cTx/j0BsnhhzIfvvB88/Dj36U6WaKiNRbQ4f/fhi7pYjPK2N5JdA+oV47YHkd5e2qKa+Wu49192J3L27dunUDm54ZiUuc/Hj+WvYvPRHuvRcuvRRef11BRERyVkMDyVSgauTVAGBKQnn/OHqrO/Bx7AKbDvQws5Yxyd4DmB4/+9TMusfRWv0TjpVXSjuW0v6LbXhkEjw0aVNYF6u8HK69FrbdNtPNExFpsDq7tszsQaAU2NXMKgmjr0YAk81sILAEOClWfwroA1QAXwBnALj7ajMbBsyN9a5296oE/tmEkWHbAdPiI7+4UzK7gkV3bANfbuCDwf/HnsNGw9aaxiMiuc/CYKncU1xc7OXl5ZluRt2WLQtLuz/5JPzwhzBuXMiJiIg0MTOb5+4pXxpDS6Sk0LeWOHGHu++GAw6AZ58Ne6Y//7yCiIjkHfWtpEjiqKxOn27NK+UH03L2HDjiiHAXss8+mW6iiEhaKJCkyOzFs1m3YS1nzNvEDc9sZFubB7fcAuecox0LRSSvKZCkSI/mXSi+D46rgNmdtmKnCQ9wyI9OzHSzRETSTv+r3FjucO+9dO0xgKOXNWP6BT+l+aznFUREpGDojqQxPvwQzjoLHn8cfvQjiu6+m57KhYhIgVEgqYdvrZX1yvIQRD79FEaNgt/9DoqKMt1EEZEmp0CSpKpRWTt8upZO04ySNzdC164wYULYwVBEpEApkCRp9uLZ/PfCtdz12CZafwHPDzyWI29/CrbZJtNNExHJKCXbk/HVVwwY/wbT7t3Emu3gyLOas83QqxVERETQHUnd3noLTj2VPebPZ8XpJ/LUaf/Fjfsd981+IiIiBU6BpCbucOutcNFFsPPO8OSTtOnTh4sy3S4RkSyjQLKZsqVlzJ33N35186ywxMnxx8Ndd2nbWxGRGiiQJChbWsaoS0u5/bF1bLsW3rv2QvYaMhKsuo0cRUQElGz/xqZNbLrsUh65bx3LvwOHnbkVk45opSAiIlIH3ZEAfPIJ/PKXHP632dzdtYhz+zg0b05px9JMt0xEJOspkCxaBH37hucxY/je8QdxxQfPhdnrGpklIlKnrAkkZtYLuBkoAv7q7iPSftLp06Ffv7C0yYwZUFpKCVDS4YdpP7WISL7IihyJmRUBY4DeQBfgFDNL37oj7nDDDdCnD3ToAOXlUFqattOJiOSzrAgkwGFAhbu/5+7rgIlA33ScaM6i2czv3RUuvBB+9jN46SXo2DEdpxIRKQjZEkjaAksT3lfGspR6Zf50tj7qaP5r+mv88ZitKbvhAthhh1SfRkSkoGRLIKlujK1vUclskJmVm1n5qlWr6n2SmavLWbgL9O0Hw450Zn/wXEPaKiIiCbIlkFQC7RPetwOWb17J3ce6e7G7F7du3breJynd62j+7+RteXL/IpoVNdPwXhGRFMiWUVtzgc5m1glYBvQDTk31SUralzCz/8xvNqfS8F4RkUbLikDi7hvM7DxgOmH47zh3X5COc5W0L1EAERFJoawIJADu/hTwVKbbISIi9ZMtORIREclRCiQiItIoCiQiItIoCiQiItIoCiQiItIo5r7FBPKcYGargA8a+PVdgf+ksDm5olCvGwr32gv1uqFwr722697T3es/m7sOORtIGsPMyt29ONPtaGqFet1QuNdeqNcNhXvtmbhudW2JiEijKJCIiEijFGogGZvpBmRIoV43FO61F+p1Q+Fee5Nfd0HmSEREJHUK9Y5ERERSpKACiZn1MrOFZlZhZoMz3Z5kmVl7M5tlZu+Y2QIzOz+WtzKzGWa2KD63jOVmZqPjdb5pZockHGtArL/IzAYklHc1s/nxO6PNzGo7RxNff5GZvWZmT8T3nczs5dimSWbWLJY3j+8r4ucdE44xJJYvNLOeCeXV/p2o6RxNycxamNnDZvZu/O1LCuE3N7ML4t/zt8zsQTPbNl9/czMbZ2YrzeythLKM/ca1naNW7l4QD8Ly9P8C9gKaAW8AXTLdriTb3gY4JL7eEfgn0AUYCQyO5YOB6+PrPsA0ws6T3YGXY3kr4L343DK+bhk/ewUoid+ZBvSO5dWeo4mv//fAA8AT8f1koF98fQdwdnx9DnBHfN0PmBRfd4m/d3OgU/x7UFTb34maztHE1z0e+N/4uhnQIt9/c8IW2+8D2yX8Dqfn628OHAkcAryVUJax37imc9R5HU39H0emHvEPc3rC+yHAkEy3q4HXMgU4DlgItIllbYCF8fWdwCkJ9RfGz08B7kwovzOWtQHeTSj/ul5N52jCa20HzASOBp6If8H/A2y9+e9K2M+mJL7eOtazzX/rqno1/Z2o7RxNeN07Ef5Btc3K8/o3JwSSpfEfxa3jb94zn39zoCPfDiQZ+41rOkdd11BIXVtVf0GrVMaynBJv3Q8GXgZ2d/cVAPF5t1itpmutrbyymnJqOUdT+TNwMbApvt8F+MjdN8T3iW39+vri5x/H+vX986jtHE1lL2AVcLeFbr2/mtkO5Plv7u7LgFHAEmAF4TecR2H85lUy+Rs36N/JQgokVk1ZTg1ZM7PvAI8Av3P3T2qrWk2ZN6A8o8zseGClu89LLK6mqtfxWS7+eWxN6PK43d0PBj4ndEHUJBevcQuxr74voTtqD2AHoHc1VfPxN69LU1xTg/4cCimQVALtE963A5ZnqC31ZmbbEILI/e7+aCz+0MzaxM/bACtjeU3XWlt5u2rKaztHUzgc+KmZLQYmErq3/gy0MLOq3T0T2/r19cXPdwZWU/8/j//Uco6mUglUuvvL8f3DhMCS77/5scD77r7K3dcDjwI/pDB+8yqZ/I0b9O9kIQWSuUDnODKjGSExNzXDbUpKHGlxF/COu9+Y8NFUoGqExgBC7qSqvH8cgdEd+Djevk4HephZy/h/fj0I/cArgE/NrHs8V//NjlXdOdLO3Ye4ezt370j4vZ5199OAWcCJ1bQpsa0nxvoey/vFET6dgM6EJGS1fyfid2o6R5Nw938DS81sv1h0DPA2ef6bE7q0upvZ9rFdVded9795gkz+xjWdo3ZNkUzKlgdhRMI/CaM2Lst0e+rR7h8Rbi/fBF6Pjz6Eft2ZwKL43CrWN2BMvM75QHHCsX4NVMTHGQnlxcBb8Tu38s1k1WrPkYE/g1K+GbW1F+EfhQrgIaB5LN82vq+In++V8P3L4rUtJI5cqe3vRE3naOJrPggoj7/744QROXn/mwN/BN6NbbuXMPIqL39z4EFCLmg94W5gYCZ/49rOUdtDM9tFRKRRCqlrS0RE0kCBREREGkWBREREGkWBREREGkWBREREGkWBREREGkWBREREGkWBREREGuX/A+oEvl6uNRlvAAAAAElFTkSuQmCC\n", "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "X = range(2, 1000001, 25000)\n", "Y = [len([p for p in primes if p<=x]) for x in X] # slow\n", "plt.plot(X, Y, '.g')\n", "plt.plot(X,[x / math.log(x) for x,y in zip(X, Y)], 'r-')\n", "plt.show()" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "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.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }