{ "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 set 'composite' of all composite numbers in the range $2..n$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "n = 1_000_000\n", "composite = {p for f in range(2, n + 1) for p in range(f * f, n + 1, f)}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We next compute select all the prime numbers in the range $2..n$, i.e. the non-composite numbers." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "primes = [p for p in range(2, n + 1) if p not in composite]" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "primes[:10]" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZIAAAD7CAYAAABADhLcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAgAElEQVR4nO3deXyU1dn/8c8liOKGoMiDBA0tiKKtVlIkaitKK2gXfFqp2MdClT5Y96UuYLWPWwUr7gtKi7JYBcQFat1ohF+xRjColUUpEdAEKGChFq2CwPX745zUIYTMJJlkZjLf9+s1r7nnzH3unIPIlftc9znH3B0REZH62iXTDRARkdymQCIiIg2iQCIiIg2iQCIiIg2iQCIiIg2iQCIiIg2SUiAxs8vMbJGZLTSzx81sdzNrZ2YzzWxpfG+bcP4IMys3syVm1i+hvKeZLYjf3WNmFst3M7MpsXyumRWmu6MiItI4kgYSM+sEXAwUufsRQAtgEDAcKHH3bkBJ/IyZ9YjfHw70Bx4wsxbxcmOAYUC3+Oofy4cCG9y9K3AncGtaeiciIo2uZR3Oa21mnwN7AKuAEUCf+P0EYDZwNTAAmOzum4DlZlYO9DKzFcA+7l4KYGYTgdOA52Od6+O1pgH3mZl5LbMl999/fy8sLEyx+SIiAjB//vwP3b19Oq+ZNJC4+0ozGw18AHwKvOTuL5lZB3dfHc9ZbWYHxCqdgNcSLlEZyz6Px9XLq+pUxGttMbOPgP2AD3fWrsLCQsrKylLoooiIVDGz99N9zVSGttoS7hi6AAcCe5rZWbVVqaHMaymvrU71tgwzszIzK1u3bl3tDRcRkSaRSrL9W8Byd1/n7p8DTwHHAmvMrCNAfF8bz68EOifULyAMhVXG4+rl29Uxs5ZAG2B99Ya4+1h3L3L3ovbt03pnJiIi9ZRKIPkA6G1me8SnrPoC7wAzgCHxnCHA9Hg8AxgUn8TqQkiqz4vDYBvNrHe8zuBqdaqudTrwcm35ERERyR6p5Ejmmtk04A1gC/AmMBbYC5hqZkMJwWZgPH+RmU0FFsfzL3D3rfFy5wHjgdaEJPvzsXwcMCkm5tcTnvoSEZEcYLn6i39RUZEr2S4iUjdmNt/di9J5Tc1sFxGRBlEgERHJIaUVpYycM5LSitJMN+U/Up2QKCIiGVZaUUrfiX3ZvHUzrVq0omRwCcWdizPdLN2RiIjkitkrZrN562a2+lY2b93M7BWzM90kQIFERCRn9CnsQ6sWrWhhLWjVohV9CvtkukmAhrZERHJGcediSgaXMHvFbPoU9smKYS1QIBERySqlFaW1BorizsVZE0CqKJCIiGSJbE2mJ6MciYhIlsjWZHoyCiQiIlkiW5PpyWhoS0QkS2RrMj0ZBRIRkSaUi8n0ZBRIRESaSK4m05NRjkREpInkajI9GQUSEZEmkqvJ9GQ0tCUikka15UByNZmejAKJiEiapJIDycVkejJJh7bMrLuZvZXw+peZXWpm7cxsppktje9tE+qMMLNyM1tiZv0Synua2YL43T1x73bi/u5TYvlcMytsjM6KiDSmJsmB/OMfsG1b+q/bAEkDibsvcfej3P0ooCfwb+BpYDhQ4u7dgJL4GTPrQdhz/XCgP/CAmbWIlxsDDAO6xVf/WD4U2ODuXYE7gVvT0z0RkabTqDmQzz6D226DL38ZHn00fddNg7om2/sC77n7+8AAYEIsnwCcFo8HAJPdfZO7LwfKgV5m1hHYx91LPWwUP7FanaprTQP6Vt2tiIjkiqocyE0n3pS+R3vdYfJkOOwwuOoqOO44KErrlusNVtccySDg8Xjcwd1XA7j7ajM7IJZ3Al5LqFMZyz6Px9XLq+pUxGttMbOPgP2AD+vYPhGRRtWkEwrnzIErroB58+DII2HmTPjWt9Jz7TRKOZCYWSvg+8CIZKfWUOa1lNdWp3obhhGGxjjooIOSNENEJL2abELh3/4Gw4fD009Dp04wfjycdRa0aJG0aibUZWjrFOANd18TP6+Jw1XE97WxvBLonFCvAFgVywtqKN+ujpm1BNoA66s3wN3HunuRuxe1b9++Dk0XEWm4Rk+mf/ghXHIJHH44vPQS3HRTCCpDhmRtEIG6BZIz+WJYC2AGMCQeDwGmJ5QPik9idSEk1efFYbCNZtY75j8GV6tTda3TgZdjHkVEJGs0WjL9s89g9Gjo2hXuuw/OOQfKy+Haa2GPPdLzMxpRSkNbZrYH8G3g3ITiUcBUMxsKfAAMBHD3RWY2FVgMbAEucPetsc55wHigNfB8fAGMAyaZWTnhTmRQA/okItIo0j6h0B2mTIERI2DFCjj1VPjNb8IdSQ6xXP3Fv6ioyMvKyjLdDBFphpIl1NPiL3+BX/wC5s6Fr34Vbr+9SRLpZjbf3dP62JdmtouIJGj0hHp5eUikP/kkHHggPPwwDB6c1TmQZLRoo4hIgkZLqK9fD5ddBj16wAsvwA03hET62WfndBAB3ZGIiGynKqFedUfS4IT6pk1w//3hCax//Ssk0m+8ETp2TEt7s4ECiYjknSZZodc9DF9dfTUsWwYnnxyezPrKV9LQg+yiQCIieaVJVuh97bWQSH/1VTjiiDCU1a9f8no5SjkSEckrjTqpcPlyGDQIiovhvfdg7Fh4881mHURAdyQikmfSngMB+Oc/4ZZb4O67Q+L82mvDAot7793wa+cABRIRyStpnVT4+efw0ENw/fXhqazBg+Hmm6GgIGnV5kSBRESanUZfodcd/vCHcNexZAmceGJIpB99dANanbsUSESkWWn0CYVvvBGWdp81C7p3hxkz4LvfhTzeQknJdhFpVhotmb5yJfz0p2FTqbffDosrLlgA3/teXgcR0B2JiDQzaU+mf/xxWEhx9GjYujXcjVxzDey7b1ra2xwokIhIs5K2ZPrWrWFDqWuvhb//Hc44A0aOhC5d0tre5kCBRERyTqMn0//0pzCh8O23oXdveOqpMDdEaqRAIiI5pVGT6YsXw5VXwnPPQWFh2Ctk4MC8z4Eko2S7iOSURkmmr10L558f9gV55ZWQE3nnHfjRjxREUqA7EhHJKWlNpn/2WZiNfsst8Mkn8POfw//9H7Rvn7b25oOU7kjMbF8zm2Zm75rZO2ZWbGbtzGymmS2N720Tzh9hZuVmtsTM+iWU9zSzBfG7e+Le7cT93afE8rlmVpjujopI81CVTL/pxJvqP6zlDpMnw6GHhk2mvvlNWLgwPNKrIFJnqQ5t3Q284O6HAkcC7wDDgRJ37waUxM+YWQ/CnuuHA/2BB8ysateWMcAwoFt89Y/lQ4EN7t4VuBO4tYH9EpEcVlpRysg5IymtKK3x++LOxYz4xoj6BZHSUjj2WDjzzPAI75/+FGapH3poA1udv5IGEjPbB/gmMA7A3Te7+z+BAcCEeNoE4LR4PACY7O6b3H05UA70MrOOwD7uXupho/iJ1epUXWsa0LfqbkVE8ktVMv26WdfRd2LfnQaTOluxIqzMe+yx8P77MG4czJ8Pffum5/p5LJU7ki8B64BHzOxNM/udme0JdHD31QDx/YB4fiegIqF+ZSzrFI+rl29Xx923AB8B+1VviJkNM7MyMytbt25dil0UkVyS9mT6Rx+F4atDDw3LmfzqV2GL23POyfktbrNFKoGkJXA0MMbdvwZ8QhzG2oma7iS8lvLa6mxf4D7W3Yvcvai9xjFFmqWqZHoLa9GwZPqWLTBmDHTtCrfeGu5G/va3sFf6Xnultc35LpWntiqBSnefGz9PIwSSNWbW0d1Xx2GrtQnnd06oXwCsiuUFNZQn1qk0s5ZAG2B9PfojIjliZ5MK0zIz/YUXwoTCxYvhhBPg9tuhZ880tl4SJQ0k7v53M6sws+7uvgToCyyOryHAqPg+PVaZATxmZncABxKS6vPcfauZbTSz3sBcYDBwb0KdIUApcDrwcsyjiEgzlGxSYb1npi9cGNbCevHFcCfyzDPw/e9rLkgjS3UeyUXA782sFbAMOJswLDbVzIYCHwADAdx9kZlNJQSaLcAF7r41Xuc8YDzQGng+viAk8ieZWTnhTmRQA/slIlmspjxIg2anr1kT5n/89rfQpg3cdRecdx60apW+RstOpRRI3P0toKiGr2p83MHdfw38uobyMuCIGso/IwYiEWn+0jap8LPPQtC45Rb49FO46KKQTG/XLq3tldppZruINLkG50HcwzpYw4eHR3kHDAjLmhxySOM0WGqlQCIijaLRVuh97TW47LLwftRR8MgjYatbyRgFEhFJu0ZZoff992HECHj8cejYER5+GAYP1lyQLKDVf0Uk7dI6qXDjxrAjYffu4Sms664L80HOPltBJEvojkRE0i4tyfStW8Ow1bXXhqeyzjorJNU7d05eV5qUAomIpF2Dk+klJXD55WGHwuOOC0ub9OrVOI2VBlMgEZF6aZRk+pIlYULhs8+GHQqnToXTT9eEwiynQCIidZb2ZPr69WENrAcegNatw9pYF18Mu++evkZLo1GyXUTqLG3J9M2bw4TCrl3DplJDh0J5OVx1lYJIDlEgEZE6a/AKve4h73HEEWFOSFERvPUWPPggHHBA8vqSVTS0JSJ11qBk+ttvh+Dx8sthj5A//hFOOUV5kBymQCIiNUp7Mn3NmjAHZNy4sMXtvffCuefCrrumsdWSCQokIrKDtCbTqy+seMklIaC0bZveRkvGKEciIjtISzLdPTy+e9hhYWmTk04KG03dcYeCSDOjQCIiO2hwMv311+Eb34Azzgj7g5SUhOVNunVrlPZKZmloS0R2UO9k+sqV4e5j0iTo0CFsNKU1sZq9lAKJma0ANgJbgS3uXmRm7YApQCGwAviRu2+I548AhsbzL3b3F2N5T77YIfE54BJ3dzPbDZgI9AT+AZzh7ivS0kMRqVFak+n//jfcdlvYE2Tr1hBMRoyAvfdOc6slG9XljuREd/8w4fNwoMTdR5nZ8Pj5ajPrQdgq93DCnu1/MrND4na7Y4BhwGuEQNKfsN3uUGCDu3c1s0HArcAZDeybiOxE2pLp27bBY4+FDaZWroQf/SjMSi8sTHubJXs1JEcyAJgQjycApyWUT3b3Te6+HCgHeplZR2Afdy91dyfcgZxWw7WmAX3N9FC5SGNJSzL91VehuBh+8pOwP8icOWHXQgWRvJNqIHHgJTObb2bDYlkHd18NEN+rpqN2AioS6lbGsk7xuHr5dnXcfQvwEbBf3boiIqlqUDL9/ffhzDPDqryVlTBhAsydC8cf32jtleyW6tDWce6+yswOAGaa2bu1nFvTnYTXUl5bne0vHILYMICDDjqo9haLyE7zIPVKpn/8cRi2Gj06fL7uurAm1l57NVLrJVekFEjcfVV8X2tmTwO9gDVm1tHdV8dhq7Xx9EogceeZAmBVLC+ooTyxTqWZtQTaAOtraMdYYCxAUVHRDoFGRL6QLA+ScjJ927bwFNaIEbB6Nfz4xzByJOiXOYmSDm2Z2Z5mtnfVMXAysBCYAQyJpw0BpsfjGcAgM9vNzLoA3YB5cfhro5n1jvmPwdXqVF3rdODlmEcRkXpKSx7klVfChlI//WkIHK++Cr//vYKIbCeVO5IOwNMx990SeMzdXzCz14GpZjYU+AAYCODui8xsKrAY2AJcEJ/YAjiPLx7/fT6+AMYBk8ysnHAnMigNfRPJaw3a7nbFCrj66jAzvaAAHn005EV20Rxm2ZHl6i/+RUVFXlZWlulmiGS1ZHNFdrBxI4waBbffHiYRXnUVXHkl7LFH4zdWmoSZzXf3onReUzPbRXJY2iYVbtsWnr665hr4+9/hrLNCHqSgIHldyXsKJCI5Km2TCufMgUsvhTfegN69w5pYxxyT/gZLs6UBT5Ec1eBk+ooVYSb6N78Ja9eGGeqvvqogInWmQCKSo+o9qfDjj+GXv/xid8IbboAlS0IyXQtKSD1oaEskR9V5UuG2bTBxYpgPojyIpJECiUgWS1sy/ZVXQh5k/vwwdPX00yEfIpIGCiQiWSotyfT33w/zQaZMgU6dNB9EGoX+NolkqQYl0z/5BH71q5AHmT49HC9ZAv/zPwoikna6IxHJUvWamV59f5BBg8JCi1rSRBqRAolIlqpzMn3uXLjkkvDes2cYzjruuKZprOQ1BRKRDEpLMn3lynAH8uij8F//BY88AoMHawhLmowCiUiGNDiZ/umnYW+QUaO0T7pklH5lEcmQeifT3cOqvIcdFpLo/fvDO+/ALbcoiEhGKJCIZEi9Zqa/+SaccAKccQa0aQOzZsGTT0KXLo3eXpGd0dCWSIbUKZm+Zg1cey2MGwf77QcPPQRDh4al3kUyTIFEpBE1OJm+eTPccw/ceGPIiVx2Wdgrfd99G7HVInWjQCLSSBqUTHeHZ5+FX/wCli6F73wnbDbVvXvjNlqkHlLOkZhZCzN708yejZ/bmdlMM1sa39smnDvCzMrNbImZ9Uso72lmC+J398S924n7u0+J5XPNrDB9XRTJjHon0xcvDgn0738/PML73HMhqCiISJaqS7L9EuCdhM/DgRJ37waUxM+YWQ/CnuuHA/2BB8ysaiB3DDAM6BZf/WP5UGCDu3cF7gRurVdvRLJInZPpGzaECYVf/WqYVHjnnbBgAZxySpO0V6S+UgokZlYAfAf4XULxAGBCPJ4AnJZQPtndN7n7cqAc6GVmHYF93L3Uw0bxE6vVqbrWNKBv1d2KSK6qSqbfdOJNtQ9rbdkCY8ZAt25w333ws5+F4axLL4Vdd23aRovUQ6o5kruAq4DEh9Q7uPtqAHdfbWYHxPJOwGsJ51XGss/jcfXyqjoV8VpbzOwjYD/gw9S7IpIZtSXUkybTZ80KAePtt8NjvXfdBUcd1cgtFkmvpIHEzL4LrHX3+WbWJ4Vr1nQn4bWU11aneluGEYbGOEiL0EkWqHdCfflyuPLKMAfk4IPhiSfghz/UDoWSk1IZ2joO+L6ZrQAmAyeZ2aPAmjhcRXxfG8+vBDon1C8AVsXyghrKt6tjZi2BNsD66g1x97HuXuTuRe3bt0+pgyKNqc4J9U8+CY/vHnZYSKLfeGOYlX766QoikrOSBhJ3H+HuBe5eSEiiv+zuZwEzgCHxtCHA9Hg8AxgUn8TqQkiqz4vDYBvNrHfMfwyuVqfqWqfHn7HDHYlItkk5oe4elnfv3h1uvjncfSxZEoJK69ZN2maRdGvIPJJRwFQzGwp8AAwEcPdFZjYVWAxsAS5w962xznnAeKA18Hx8AYwDJplZOeFOZFAD2iXSZFKanT5/Plx8Mbz6Khx9tJZ3l2bHcvUX/6KiIi8rK8t0MyQPJJudvlNr1sAvfwkPPwzt28PIkfDTn2p5d8koM5vv7kXpvKZmtovUol7J9M2b4d57Q/7j3/+Gyy8PQ1ht2jRNo0WamH41EqlFnZPpzz8fJhRecUUYvlq4MOwZoiAizZgCiUgtUk6mL10K3/0unHpq2Df9j38MT2VpWRPJAxraEqlF0mT6xo3hKaw774Tdd4fbbguJ9VatMtNgkQxQIJG8V6+l3rdtC3ukX301/P3vIYk+cmTYM10kzyiQSF6rVzL99dfhoovCworHHAPTp0OvXk3TYJEspByJ5LU6JdPXrAm7EvbqBStWwPjxYW6IgojkOQUSyWspJdM3b4Y77oBDDoFJk8IaWX/7GwwZojkhImhoS/Jc0mT6Sy+FPULefTfsC3LXXSGgiMh/KJBIs1evZPqyZWEi4fTp0LUr/OEP4fFeEdmBAok0a3VOpn/ySXj6avRoaNkSRo0K+4XstlvTNVokx2iAV5q1lJPp7mExxUMPhV//GgYODHmQq69WEBFJQoFEmrWUkulvvw19+sCgQWFxxVdeCUn1Aw9s6uaK5CQNbUmzVmsyff36sJjigw9C27bw0EPh8d4WLTLXYJEcpEAiOa/OyfStW+F3vwtLvG/YAOefH1bqbdu2CVst0nwokEhOq3My/S9/CbPS33wTTjgB7rknrNYrIvWmHInktJST6atWwU9+AscfD+vWweTJMGuWgohIGiQNJGa2u5nNM7O/mtkiM7shlrczs5lmtjS+t02oM8LMys1siZn1SyjvaWYL4nf3xL3bifu7T4nlc82sMP1dleYoaTJ982b4zW/Ccu5Tp8I114TJhWecAeGvn4g0UCp3JJuAk9z9SOAooL+Z9QaGAyXu3g0oiZ8xsx6EPdcPB/oDD5hZVfZyDDAM6BZf/WP5UGCDu3cF7gRuTUPfJA9UJdNvOvGmHYe1XnwRvvKV8Ahvnz6waFF4tHfPPTPWXpHmKGkg8eDj+HHX+HJgADAhlk8ATovHA4DJ7r7J3ZcD5UAvM+sI7OPupR42ip9YrU7VtaYBfavuVkQg5EJGzhlJaUXpDt8Vdy5mxDdGfBFEli+H006D/v2/2GTqD38IM9RFJO1SSrbHO4r5QFfgfnefa2Yd3H01gLuvNrMD4umdgNcSqlfGss/jcfXyqjoV8VpbzOwjYD/gw3r1SpqVlBPq//433HpreLVoEWaoX3aZJhSKNLKUku3uvtXdjwIKCHcXR9Ryek13El5LeW11tr+w2TAzKzOzsnXr1iVrtjQTSRPq7vDUU9CjR3iM97//G5YsgeHDFUREmkCdntpy938Cswm5jTVxuIr4vjaeVgl0TqhWAKyK5QU1lG9Xx8xaAm2A9TX8/LHuXuTuRe3bt69L0yWH1ZpQf/dd6NcPfvhD2Hvv8CTW449DQcFOryci6ZXKU1vtzWzfeNwa+BbwLjADGBJPGwJMj8czgEHxSawuhKT6vDgMttHMesf8x+BqdaqudTrwcsyjiNScUN+4Ea66KiTT580Ly7u/+WZIqotIk0olR9IRmBDzJLsAU939WTMrBaaa2VDgA2AggLsvMrOpwGJgC3CBu2+N1zoPGA+0Bp6PL4BxwCQzKyfciQxKR+ckd6Q8O9093HFccUWYG3L22SEX0qFDBlotIgCWq7/4FxUVeVlZWaabIWmQcjJ9wQK48EL485/h6KPh/vuhd++mb7BIDjOz+e5elM5rama7ZFzSZPo//xn2BPna12DhwrC44rx5CiIiWUJrbUnGVSXTq+5I/pNM37YtLOd+1VVhWZNzz4Wbb4b99stoe0VkewokknE1LvX+1ltwwQXw6qtwzDHw3HPQs2emmyoiNVAgkSaRcjJ9w4aQBxkzJtx5PPwwDBkCu2gUViRbKZBIo0spmb5tG4wfHyYR/uMf2iNEJIfo1zxpdEmT6W+8AccdF3YnPOQQmD8f7r1XQUQkRyiQSKPb6cz09evDnUdRUVhoccIEmDMHjjoqo+0VkbrR0JY0uh2S6Z2OCbmPq68OweTii+GGG6BNm0w3VUTqQYFE0iLlZPobb8DAY2Hu3DCcdf/9cOSRGWixiKSLAok0WErJ9A0b4Nprw9NY7duHYayf/ES7FIo0A8qRSIPVmkzftg0eeSQk0R98MDzau2QJDB6sICLSTCiQSIPtNJn+17/CN74B55wD3bqFp7HuuQf23Tej7RWR9NLQljTYDsn0fXqEtbHuvRfatdOkQpFmToFEUpJSMr2gNzz2GFzxA1izJqyN9etfh2AiIs2WAokklVIyffHisDbW7NlhXsiMGfD1r2ekvSLStDTWIEnVmkz/+OMwH+TII0NO5MEH4bXXFERE8ojuSCSpGpd5d4ennw65kIqKkFAfNSo82isieSWVPds7m9ksM3vHzBaZ2SWxvJ2ZzTSzpfG9bUKdEWZWbmZLzKxfQnlPM1sQv7sn7t1O3N99Siyfa2aF6e+q1NcOe6ZvPgC+8x344Q/DE1ivvALjximIiOSpVIa2tgC/cPfDgN7ABWbWAxgOlLh7N6AkfiZ+Nwg4HOgPPBD3ewcYAwwDusVX/1g+FNjg7l2BO4Fb09A3qaPSilJGzhlJaUXpDt8Vdy5mxNcvo/iRmXD44WFNrDvu+GLBRRHJW0mHttx9NbA6Hm80s3eATsAAoE88bQIwG7g6lk92903AcjMrB3qZ2QpgH3cvBTCzicBpwPOxzvXxWtOA+8zMPFc3lM9BSRPqL70Ukunl5XDGGXD77dCpU+YaLCJZo07J9jjk9DVgLtAhBpmqYHNAPK0TUJFQrTKWdYrH1cu3q+PuW4CPgB32UzWzYWZWZmZl69atq0vTJYmdJtRXrgyBo1+/MBP9pZdg8mQFERH5j5QDiZntBTwJXOru/6rt1BrKvJby2upsX+A+1t2L3L2ovcbj02qH2ekFx8Ndd8Fhh8H06WGTqQUL4NvfznRTRSTLpPTUlpntSggiv3f3p2LxGjPr6O6rzawjsDaWVwKdE6oXAKtieUEN5Yl1Ks2sJdAGWF+P/kg9Jc5O/+76/fnKDy4O+6b37w/33Qdf/nKmmygiWSqVp7YMGAe84+53JHw1AxgSj4cA0xPKB8UnsboQkurz4vDXRjPrHa85uFqdqmudDrys/EjTK96zOyMeXcFX/vtcWLcOnngCnntOQUREapXKHclxwE+ABWb2Viy7BhgFTDWzocAHwEAAd19kZlOBxYQnvi5w962x3nnAeKA1Icn+fCwfB0yKifn1hKe+JM12usyJO0yaBFdcETaauuwyuP562HvvjLVVRHKH5eov/kVFRV5WVpbpZuSMnT6V9c47Ybvb2bOhd+8wM10bTYk0W2Y2392L0nlNLZGSJ6o/lfXKkplho6kjjwy5kIcegr/8RUFEROpMS6TkicRlTk5d1oKLxj0EH6wKuxSOHg0HHJD8IiIiNVAgyRPFnYv588mT2ePqa+kxawF03xtefhlOPDHTTRORHKdA0ozsNJm+dSs8+CBF11wDmzbBTTfBlVfCbrtlrrEi0mwokDQTO02mv/UWDBsGr78eJhM+8AB07Zrp5opIM6JkezNRPZn+l8Uvhsd5i4rg/ffDzoUvvqggIiJppzuSZiIxmX7a0hZcNPZBWLkm3I2MGgVt2ya/iIhIPeiOpJko7lzMnJMns7DkUKY9upnd9t0/7BPy0EMKIiLSqHRHkkNqTaaPGUPPa66BLVtg5Ei4/HJo1SpzjRWRvKFAkiN2mkx/++0wfDV3Lpx8MowZA1/6UqabKyJ5RENbOWKHmenvvgTDh0PPnrBsGTz6KLzwgoKIiDQ53ZHkiMRkev/lLbho3NgwM2+0pGgAAAs4SURBVP2cc+C226Bdu0w3UUTylAJJjijuXMz/+840Wl/1S46Y+RYcshfMmgV9+mS6aSKS5xRIckFc5v3rl10GGzfCr34FI0bA7rtnumUiIgok2aTGp7KWLYOf/xxmzoRjj4Xf/hZ69MhsQ0VEEiiQZIkdnsr68YsUPzUPrrsOWraE++8PAWUXPR8hItlFgSRLJD6V1aNyE4WnnAlLVsL3vhfWxyooSH4REZEMSGXP9ofNbK2ZLUwoa2dmM81saXxvm/DdCDMrN7MlZtYvobynmS2I390T920n7u0+JZbPNbPC9HYxN/Qp7MM+23bl1j8Zr43dxn7rP4WpU2H6dAUREclqqYyTjAf6VysbDpS4ezegJH7GzHoQ9ls/PNZ5wMxaxDpjgGFAt/iquuZQYIO7dwXuBG6tb2dyWfGyzaycsD9XveL840ffo9WSchg4EEK8FRHJWkkDibv/GVhfrXgAMCEeTwBOSyif7O6b3H05UA70MrOOwD7uXuphk/iJ1epUXWsa0LfqbqU5Kq0oZeSckZRWlIaCjz4KuY8+fWi9SysoKaHD4zO0PpaI5Iz65kg6uPtqAHdfbWZV+7R2Al5LOK8yln0ej6uXV9WpiNfaYmYfAfsBH1b/oWY2jHBXw0EHHVTPpmdO9YT6/ANv5LDr7oLVq+EXv4Abb4Q99sh0M0VE6iTdyfaa7iS8lvLa6uxY6D4WGAtQVFRU4znZrCqh3vbjrdzzwmcctuBKOOIIeOop6NUr080TEamX+j5LuiYOVxHf18bySqBzwnkFwKpYXlBD+XZ1zKwl0IYdh9KahT4Hn8BZC3fhnfvhh4udist/BvPnK4iISE6rbyCZAQyJx0OA6Qnlg+KTWF0ISfV5cRhso5n1jvmPwdXqVF3rdODlmEdpXlatovjCUYx/4nM2FXZm8QuP0vn232qpdxHJeUmHtszscaAPsL+ZVQL/B4wCpprZUOADYCCAuy8ys6nAYmALcIG7b42XOo/wBFhr4Pn4AhgHTDKzcsKdyKC09CxbuMPEiXDppfDZZzB6NJ0uvZROLVokrysikgMsV3/5Lyoq8rKyskw3YwfbLXNineHcc+G55+D442HcODjkkEw3UUTymJnNd/eidF5TM9vT6D9PZW3ZxP++1YKvl7Si5ZZtcPfdcOGFWt5ERJolBZI0mr1iNh3+sYkHZ2yj33vbeP+oAg6eNhO+/OVMN01EpNHoV+R0cWfg3I/56wPbOK4CLv3erqx6ZpKCiIg0e7ojSYfVq+F//5euf/wjHxUfzcRLTuKMY3/wxVLwIiLNmAJJQ7jDlClw/vnw6adw9920ufBCzlcuRETyiAJJHVU9lfWtfY7i679+BJ54Anr3hvHjoXv3TDdPRKTJKZDUQdVTWScv2sQ5M7axbXNLdhk5Eq64Imw+JSKShzQGUwevLn6RB6Z9xjOPb2PV3vDw2PNg+HAFERHJa/oXMFWvvcYFw37LrhXOLd80bj1pN17oe2amWyUiknEKJMls2QK33AI33sjunTuzcNqDWPv1vFDYR09liYigQFK75cvhrLPg1VfD+333cUSbNhyR6XaJiGQRBZJqSitKmb18Fqe/uYlu190ZljV57DE4U8NYIiI1USBJUFpRyg8eOok7Zmyi2wLnX72OZJ+p0+HggzPdNBGRrKVAkmDhrCnMGfMZhRvgupOMPa8byHAFERGRWimQVJkxg3PO/y0fGpx4zi7M77IbJV8+KdOtEhHJeppH4g433wwDBtDisB5UljzDqUNupmRwiZ7KEhFJQdbckZhZf+BuoAXwO3cf1eg/9JNP4OyzwzInZ50FY8fSs3VrejKg0X+0iEhzkRV3JGbWArgfOAXoAZxpZj0a9YeuWAHHHgtPPgmjR4ftcFu3btQfKSLSHGXLHUkvoNzdlwGY2WRgAGHv97QqrSjlvWce5ozrp7HrVg/b4Pbrl+4fIyKSN7IlkHQCKhI+VwLHpPuHlFaU8vClJ/DAM5/z3n7Gp089ztdOUBAREWmIrBjaAqyGMt/hJLNhZlZmZmXr1q2r8w+ZvWI277bdyvTuUPwz44VdltWnrSIikiBbAkkl0DnhcwGwqvpJ7j7W3Yvcvah9+/Z1/iF9Cvswv8tuDBrUgk177kafwj71brCIiATZMrT1OtDNzLoAK4FBwI/T/UOKOxdTMriE2Stm00eLLoqIpEVWBBJ332JmFwIvEh7/fdjdFzXGzyruXKwAIiKSRlkRSADc/TnguUy3Q0RE6iZbciQiIpKjFEhERKRBFEhERKRBFEhERKRBFEhERKRBzH2HCeQ5wczWAe/Xs/r+wIdpbE4uyde+52u/IX/7rn7X7GB3r/uM7lrkbCBpCDMrc/eiTLcjE/K17/nab8jfvqvfTUdDWyIi0iAKJCIi0iD5GkjGZroBGZSvfc/XfkP+9l39biJ5mSMREZH0ydc7EhERSZO8CyRm1t/MlphZuZkNz3R7UmFmnc1slpm9Y2aLzOySWN7OzGaa2dL43jahzojYxyVm1i+hvKeZLYjf3WNmFst3M7MpsXyumRUm1BkSf8ZSMxvSdD3/z89vYWZvmtmz8XO+9HtfM5tmZu/G//bFedT3y+Lf9YVm9riZ7d4c+25mD5vZWjNbmFCW0X6aWZd47tJYt1XSjrh73rwIS9S/B3wJaAX8FeiR6Xal0O6OwNHxeG/gb0AP4DfA8Fg+HLg1HveIfdsN6BL73CJ+Nw8oJuxK+TxwSiw/H3gwHg8CpsTjdsCy+N42Hrdt4v5fDjwGPBs/50u/JwA/i8etgH3zoe+ErbeXA63j56nAT5tj34FvAkcDCxPKMtrP+Oc9KB4/CJyXtB9N+T9Gpl/xD/rFhM8jgBGZblc9+jEd+DawBOgYyzoCS2rqF2Gfl+J4zrsJ5WcCDyWeE49bEiY0WeI58buHgDObsK8FQAlwEl8Eknzo9z6Ef0ytWnk+9L0TUBH/kWsJPAuc3Fz7DhSyfSDJWD/jdx8CLWP5dv9m7uyVb0NbVX9Bq1TGspwRb02/BswFOrj7aoD4fkA8bWf97BSPq5dvV8fdtwAfAfvVcq2mchdwFbAtoSwf+v0lYB3wSBzW+52Z7Uke9N3dVwKjgQ+A1cBH7v4SedD3KJP93A/4Zzy3+rV2Kt8CidVQljOPrZnZXsCTwKXu/q/aTq2hzGspr2+dRmVm3wXWuvv8VKvUUJZz/Y5aEoY8xrj714BPCMMcO9Ns+h5zAgMIwzcHAnua2Vm1VamhLCf7nkRT9LNe/c+3QFIJdE74XACsylBb6sTMdiUEkd+7+1OxeI2ZdYzfdwTWxvKd9bMyHlcv366OmbUE2gDra7lWUzgO+L6ZrQAmAyeZ2aM0/35XtavS3efGz9MIgSUf+v4tYLm7r3P3z4GngGPJj75DZvv5IbBvPLf6tXauqcY9s+FF+C1vGeE3napk++GZblcK7TZgInBXtfLb2D4p95t4fDjbJ+WW8UVS7nWgN18k5U6N5RewfVJuajxuRxirbxtfy4F2Gfgz6MMXOZK86DcwB+gej6+P/W72fQeOARYBe8Q2TwAuaq59Z8ccSUb7CTzB9sn285P2oSn/x8iGF3Aq4amn94BfZro9Kbb5eMLt5dvAW/F1KmE8swRYGt/bJdT5ZezjEuITHLG8CFgYv7uPLyal7h7/ApUTngD5UkKdc2J5OXB2hv4M+vBFIMmLfgNHAWXxv/sz8X/4fOn7DcC7sd2TCP94Nru+A48T8kCfE+4Shma6n4T83LxY/gSwW7J+aGa7iIg0SL7lSEREJM0USEREpEEUSEREpEEUSEREpEEUSEREpEEUSEREpEEUSEREpEEUSEREpEH+P0iymXVRVGwdAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "import math\n", "\n", "X = range(2, n + 1, 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.8.1" } }, "nbformat": 4, "nbformat_minor": 2 }