{"id":123,"date":"2021-10-27T19:30:32","date_gmt":"2021-10-27T19:30:32","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=123"},"modified":"2024-05-17T20:31:19","modified_gmt":"2024-05-17T20:31:19","slug":"algoritm-low-memory-pentru-numere-prime","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/algoritm-low-memory-pentru-numere-prime\/","title":{"rendered":"Algoritm low-memory pentru numere prime"},"content":{"rendered":"\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<p class=\"has-text-align-left\">     Determinarea primalit\u0103\u021bii unui num\u0103r reprezint\u0103 o sarcin\u0103 de lucru pe care o putem \u00eent\u00e2lni at\u00e2t la probleme simple, c\u00e2t \u0219i la probleme cu un grad ridicat de dificultate, cum ar fi cele de olimpiad\u0103. Este foarte important s\u0103 observ\u0103m resursele disponibile atunci c\u00e2nd rezolv\u0103m o astfel de problem\u0103. \u00cen cazul \u00een care avem destul\u0103 memorie la dispozi\u021bie, putem utiliza <em><a href=\"https:\/\/www.geeksforgeeks.org\/sieve-of-eratosthenes\/\" data-type=\"URL\" data-id=\"https:\/\/www.geeksforgeeks.org\/sieve-of-eratosthenes\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>ciurul lui Eratostene<\/strong><\/a><\/em>, fie el sub forma unui vector bool, fie utiliz\u00e2nd <em><a href=\"https:\/\/www.geeksforgeeks.org\/c-bitset-and-its-application\/\" data-type=\"URL\" data-id=\"https:\/\/www.geeksforgeeks.org\/c-bitset-and-its-application\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>&lt;bitset&gt;<\/strong><\/a><\/em>. Exist\u0103 \u00eens\u0103 cazuri \u00een care memoria nu ne permite s\u0103 folosim astfel de structuri, prin urmare, vom fi nevoi\u021bi s\u0103 ne g\u00e2ndim la o alt\u0103 metod\u0103 pentru determinarea primalit\u0103\u021bii unui num\u0103r. Probabil c\u0103, mul\u021bi vor tinde s\u0103 utilizeze urm\u0103torul algoritm:<\/p>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"765\" height=\"596\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-88-1.png\" alt=\"\" class=\"wp-image-151\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-88-1.png 765w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-88-1-300x234.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-88-1-500x390.png 500w\" sizes=\"auto, (max-width: 765px) 100vw, 765px\" \/><\/figure>\n\n\n\n<p>      Este un algoritm simplu, u\u0219or de \u00een\u021beles, dar care nu este foarte eficient. Avem nevoie de ceva mai bun. <\/p>\n\n\n\n<p>     Orice num\u0103r \u00eentreg, <em>x \u2208 \u2124<\/em>, \u00eel putem scrie sub forma <em>6k + p<\/em>, unde <em>p \u2208 {-1, 0, 1, 2, 3, 4}<\/em>, <em>k \u2208 \u2124<\/em>. Acest lucru ne va ajuta foarte mult. S\u0103 ne folosim de acest\u0103 informa\u021bie:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>dac\u0103 <em>p \u2208 {0, 2, 4}<\/em>, atunci <em>x = 6k<\/em>,<em> x = 6k + 2<\/em> sau <em>x = 6k + 4 <\/em>&lt;=&gt;<em> x = 2 * 3k<\/em>, <em>x = 2 * (3k + 1)<\/em> sau <em>x = 2 * (3k + 2)<\/em> =&gt; x este divizibil cu 2 =&gt; <strong>x nu este prim.<\/strong> <em>(1)<\/em><\/li><li>dac\u0103 <em>p \u2208 {3}<\/em>, atunci <em>x = 6k + 3<\/em> &lt;=&gt; <em>x = 3 * (2k + 1)<\/em> =&gt; x este divizibil cu 3 =&gt; <strong>x nu este prim.<\/strong> <em>(2)<\/em><\/li><\/ul>\n\n\n\n<p><\/p>\n<\/div><\/div>\n\n\n\n<p>     R\u0103m\u00e2nem, deci, cu <em>p = \u00b1 1<\/em> =&gt; <em>x = 6k \u00b1 1<\/em>, despre care dorim s\u0103 afl\u0103m dac\u0103 este prim. Haide\u021bi s\u0103 arunc\u0103m o privire asupra perechilor de forma <em>(6k \u2013 1, 6k + 1)<\/em>, <em>k \u2265 1<\/em>: <em>(5, 7)<\/em>, <em>(11, 13)<\/em>, <em>(17, 19)<\/em>, <em>(23, 25)<\/em>, \u2026 Pentru aceste numere, vom \u00eencerca s\u0103 g\u0103sim divizori pentru a verifica dac\u0103 sunt numere prime sau nu. <strong>Divizorii acestor numere vor fi tot de forma <em>6k \u00b1 1<\/em><\/strong>, \u00eentruc\u00e2t, dac\u0103 <strong>x ar fi divizibil<\/strong> cu un num\u0103r scris sub forma <em>(1)<\/em>, atunci ar fi multiplu de <em>2<\/em>, deci nu poate fi prim (analog pentru multiplii de <em>3<\/em>, conform a ceea ce am zis la <em>(2)<\/em>). <\/p>\n\n\n\n<p>     Observ\u0103m c\u0103, modulul diferen\u021bei dintre cei 2 termeni ai unei perechi <em>(6k \u2013 1, 6k + 1)<\/em>, <em>k \u2265 1<\/em>, este mereu <strong>2<\/strong>, iar modulul diferen\u021bei dintre oricare 2 termeni afla\u021bi pe prima pozi\u021bie \u00een perechi consecutive va fi mereu <strong>6<\/strong>, datorit\u0103 <em>6k.<\/em> De observat este c\u0103, numerele prime 2 \u0219i 3 nu pot fi scrise sub forma <em>6k \u2013 1<\/em> sau <em>6k + 1<\/em>, <em>k \u2265 1<\/em>, deci va trebui s\u0103 ne ocup\u0103m separat de ele. Acestea fiind spuse, s\u0103 arunc\u0103m o privire asupra noului test de primalitate:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"710\" height=\"547\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-86.png\" alt=\"\" class=\"wp-image-143\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-86.png 710w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-86-300x231.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Screenshot-86-500x385.png 500w\" sizes=\"auto, (max-width: 710px) 100vw, 710px\" \/><\/figure>\n\n\n\n<p>     O problem\u0103 care necesit\u0103 un astfel de algoritm este&nbsp;<a href=\"https:\/\/www.pbinfo.ro\/probleme\/3502\/hard-prime\" target=\"_blank\" rel=\"noreferrer noopener\"><em>#hard_prime<\/em><\/a>&nbsp;, \u00een care solu\u021bia se \u00eencadreaz\u0103 \u00een timp \u0219i memorie folosind acest algoritm. Spor la lucru!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Determinarea primalit\u0103\u021bii unui num\u0103r reprezint\u0103 o sarcin\u0103 de lucru pe care o putem \u00eent\u00e2lni at\u00e2t la probleme simple, c\u00e2t \u0219i &hellip; <\/p>\n","protected":false},"author":3,"featured_media":145,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[24,23,22,25],"class_list":["post-123","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-probleme","tag-algoritm","tag-low_memory","tag-numere-prime","tag-olimpiada"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/123","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/comments?post=123"}],"version-history":[{"count":9,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/123\/revisions"}],"predecessor-version":[{"id":199,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/123\/revisions\/199"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/145"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}