{"id":1766,"date":"2022-05-01T16:36:05","date_gmt":"2022-05-01T19:36:05","guid":{"rendered":"http:\/\/localhost\/?page_id=1766"},"modified":"2022-05-01T16:52:29","modified_gmt":"2022-05-01T19:52:29","slug":"numero-dos-primos","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/numero-dos-primos\/","title":{"rendered":"N\u00famero dos primos"},"content":{"rendered":"<div style=\"color:#000000\">Para $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 > \\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 Julia deste algoritmo \u00e9 o seguinte. <\/p>\n<pre><code class=\"language-python\">\nfunction eratosthenes( n )\n\tprims = [ true for i in 1:n ]\n\tprims[1] = false\n\t\n\tsqrn = convert( Int64, floor(n^(1\/2)))\n\t\n\tfor i in 2:sqrn\n\t\tif prims[i] == true\n\t\t\tst = i^2\n\t\t\twhile st &lt;= n\n\t\t\t\tprims[st] = false\n\t\t\t\tst += i\n\t\t\tend\n\t\tend\n\tend\n\t\n\treturn prims\t\nend\n<\/code>\r\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$ pode ser calculado com a fun\u00e7\u00e3o acima:<\/p>\n<pre><code class=\"language-pythonrepl\">\njulia&gt; pr = eratosthenes( 10^7 );\n\njulia&gt; counter( pr )\nAccumulator{Bool, Int64} with 2 entries:\n  0 =&gt; 9335421\n  1 =&gt; 664579\n  <\/code><\/pre>\n<p>Obtemos que<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.\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\/algebra-a\/numero-dos-primos\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">N\u00famero dos primos<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1766"}],"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=1766"}],"version-history":[{"count":4,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1766\/revisions"}],"predecessor-version":[{"id":1770,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1766\/revisions\/1770"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/706"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}