{"id":1368,"date":"2021-11-02T12:20:02","date_gmt":"2021-11-02T15:20:02","guid":{"rendered":"http:\/\/localhost\/?page_id=1368"},"modified":"2023-01-06T14:44:53","modified_gmt":"2023-01-06T17:44:53","slug":"o-numero-dos-primos","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/o-numero-dos-primos\/","title":{"rendered":"O n\u00famero dos primos"},"content":{"rendered":"<div style=\"color:black;\">\nPara $n\\in\\N$, defina<br \/>\n\\[<br \/>\n\\pi(n)=|\\{k\\in\\{2,\\ldots,n\\}\\mid k\\mbox{ \u00e9 primo}\\}|.<br \/>\n\\]<br \/>\nOu seja, $\\pi(n)$ \u00e9 o n\u00famero dos primos entre $2$ e $n$. \u00c9 f\u00e1cil computar o valor de $\\pi(n)$ para $n$ pequeno:<br \/>\n\\[<br \/>\n\\pi(1)=0,\\quad \\pi(2)=1,\\quad \\pi(3)=\\pi(4)=2,\\quad \\pi(5)=\\pi(6)=3,\\ldots<br \/>\n\\]<br \/>\nNo entanto, se $n$ for grande, determinar o valor de $\\pi(n)$ pode ser dif\u00edcil.<\/p>\n<p>O Crivo de <a href=\"https:\/\/pt.wikipedia.org\/wiki\/Erat%C3%B3stenes\">Erat\u00f3stenes<\/a>, \u00e9 um algoritmo que pode ser usado para obter os primos que s\u00e3o menores ou iguais a um n\u00famero fixo $n$. A ideia do crivo \u00e9 a seguinte. Assuma que voc\u00ea quer determinar todos os primos entre $1$ e algum outro n\u00famero $n$.<\/p>\n<ul>\n<li>Escreva os n\u00fameros de $1$ at\u00e9 $n$ em uma lista na ordem crescente.<\/li>\n<li>Comece por eliminar o n\u00famero $1$ da sua lista, pois ele n\u00e3o \u00e9 primo.<\/li>\n<li>O menor n\u00famero n\u00e3o eliminado na lista \u00e9 $2$ que \u00e9 primo. Elimine os m\u00faltiplos de $2$ a partir de $4$ da lista, pois eles n\u00e3o s\u00e3o primos.<\/li>\n<li>Menor n\u00famero n\u00e3o eliminado depois de $2$ \u00e9  o $3$. Elimine os m\u00faltiplos de $3$ a partir de $3^2=9$ da lista, pois eles n\u00e3o s\u00e3o primos.<\/li>\n<li>O menor n\u00famero n\u00e3o eliminado depois de $3$ \u00e9 o $5$. Ele \u00e9 primo. Elimine os m\u00faltiplos de $5$ da lista a partir de $5^2=25$, pois eles n\u00e3o s\u00e3o primos.<\/li>\n<li>No passo geral, ache o menor n\u00famero $p$ depois do \u00faltimo primo encontrado. Este n\u00famero $p$ ser\u00e1 primo. Elimine os m\u00faltiplos de $p$ a partir de $p^2$ da lista, pois eles n\u00e3o s\u00e3o primos. Note que os demais m\u00faltiplos compostos de $p$ (que s\u00e3o menores de $p^2$) j\u00e1 foram eliminados.<\/li>\n<li>Repita o passo geral at\u00e9 $p &gt; \\sqrt n$.<\/li>\n<li>Os n\u00fameros que n\u00e3o foram eliminados da lista s\u00e3o os primos entre $1$ e $n$.<\/li>\n<\/ul>\n<p>Uma implementa\u00e7\u00e3o simples em Python deste algoritmo \u00e9 o seguinte.<\/p>\n<pre><code class=\"language-python\">\ndef eratosthenes( n ):\n    prims = [ True for i in range(n+1) ]\n    prims[0] = False; prims[1] = False\n    \n    sqrn = int(n**(1\/2))\n    \n    for i in range(2,sqrn+1):\n        if prims[i]: \n            st = i**2\n            while st &lt;= n:\n                prims[st] = False\n                st = st + i\n                \n    return prims\n<\/code>\n<\/pre>\n<p>O Crivo de Erat\u00f3stenes n\u00e3o \u00e9 um algoritmo eficiente, pois o passo geral precisa ser executada $\\sqrt n$ vezes. Na pr\u00e1tica (por exemplo, na criptografia), n\u00f3s precisamos lidar com n\u00fameros com $500$ ou mais algarismos. Se por exemplo, $n\\approx 10^{500}$, ent\u00e3o $\\sqrt n\\approx 10^{250}$ e na pr\u00e1tica fica imposs\u00edvel realizar a computa\u00e7\u00e3o at\u00e9 com um supercomputador.<\/p>\n<p>Est\u00e1 bem conhecido que a fun\u00e7\u00e3o $\\pi(n)$ pode ser aproximada pelas fun\u00e7\u00f5es<br \/>\n\\[<br \/>\n\\lambda(n)=\\frac n{\\log n}<br \/>\n\\]<br \/>\ne<br \/>\n\\[<br \/>\n\\sigma(n)=\\int_2^n \\frac{dt}{\\log t}.<br \/>\n\\]<br \/>\nPor exemplo, o n\u00famero dos primos entre $1$ e $10.000.000$ \u00e9 $664579$. Ou seja<br \/>\n\\[<br \/>\n\\pi(10.000.000)=664579,<br \/>\n\\]<br \/>\nenquanto<br \/>\n\\[<br \/>\n\\lambda(10.000.000)\\approx 620420\\quad\\mbox{e}\\quad \\sigma(10.000.000)\\approx 664917.<br \/>\n\\]<br \/>\nGeralmente, a aproxima\u00e7\u00e3o dada por $\\sigma(n)$ \u00e9 melhor, mas \u00e9 mais dif\u00edcil de calcular.<\/p>\n<p>Atualmente (novembro de 2021), o <a href=\"https:\/\/pt.wikipedia.org\/wiki\/Maior_n%C3%BAmero_primo_conhecido\">maior primo conhecido<\/a> \u00e9 $2^{82.589.933} \u2212 1$. Este n\u00famero tem $24.862.048$ algarismos na base decimal e foi encontrado em 2018. Este n\u00famero \u00e9 um exemplo dos <a href=\"https:\/\/pt.wikipedia.org\/wiki\/Primo_de_Mersenne\">primos de Mersenne<\/a>, ou seja primos na forma $2^p-1$ onde $p$ \u00e9 um primo.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Para $n\\in\\N$, defina \\[ \\pi(n)=|\\{k\\in\\{2,\\ldots,n\\}\\mid k\\mbox{ \u00e9 primo}\\}|. \\] Ou seja, $\\pi(n)$ \u00e9 o n\u00famero dos primos entre $2$ e $n$. \u00c9 f\u00e1cil computar o valor de $\\pi(n)$ para $n$ pequeno: \\[ \\pi(1)=0,\\quad \\pi(2)=1,\\quad \\pi(3)=\\pi(4)=2,\\quad \\pi(5)=\\pi(6)=3,\\ldots \\] No entanto, se $n$ for grande, determinar o valor de $\\pi(n)$ pode ser dif\u00edcil. O Crivo de Erat\u00f3stenes, &hellip; <a href=\"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/o-numero-dos-primos\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">O n\u00famero dos primos<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1193,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1368"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=1368"}],"version-history":[{"count":10,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1368\/revisions"}],"predecessor-version":[{"id":1983,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1368\/revisions\/1983"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1193"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}