• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Ciurul lui Eratostene – sursă + problemă rezolvată

7
  • Publicat de Bogdan Condurache
  • în C/C++
  • — 21 ian., 2012 at 10:00 am

Sift the Two’s and sift the Three’s, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime.

Ciurul lui Eratostene este unul dintre algoritmii foarte importanți și este des întâlnit. Acesta este folosit pentru a determina primele n numere prime.

Cerinţa

Spunem că un numar natural x este prim dacă și numai daca x > 1 si singurii săi divizori sunt 1 si x. Dându-se un numar natural N (2 ≤ N ≤ 2 000 000), să se determine numărul numerelor prime mai mici sau egale cu N.

Date de intrare

Fișierul de intrare ciur.in conține o singură linie pe care se află numarul N.

Date de ieşire

In fisierul de iesire ciur.out se va scrie pe prima linie raspunsul cerut.

Exemplu

Dacă fișierul de intrare conține numărul 10, în fișierul de ieșire va trebui să apară numărul 4.

Ideea de baza

În primul rând vom da fiecărui element din vector valoarea 1, presupunând astfel că el este prim. Poziția unui element din vector va reprezenta chiar acel număr. Vectorul este alcătuit din variabile booleene, astfel, dacă valoarea lui a[i] este egală cu 1, atunci numărul i este prim.

Rezolvarea

Vom folosi două for-uri pentru a determina dacă numărul este prim sau nu. Primul începe de la 2 și continuă până la radical din n. Al doilea este inclus în primul și face parcurgerea de la i până la n/i. Apoi, fiecare număr care se obține prin intermediul produsului acestor 2 numere este  eliminat, el nemaiputând fi prim pentru că are divizori. În sfârșit, un for final va parcurge vectorul de la 2 până la n, iar pentru fiecare număr a cărui corespondent din vector este 1 contorul (inițializat cu 0) va fi incrementat. Apoi se va face afișarea contorului, adică a numărului de numere prime mai mici ca n.

Codul

#include <fstream>
#include <math.h>

using namespace std;

int main() {
ifstream fin;
ofstream fout;
fin.open("ciur.in");
fout.open("ciur.out");
bool a[2000001];
int nr=0, n, i, j;
fin>>n;
for (i=2;i<=n;i++)  
  a[i]=1;
for (i=2;i<=sqrt(n);i++)
 if (a[i])
  for (j=i;j<=n/i;j++)
     a[i*j]=0;
for (i=2;i<=n;i++)
  if (a[i]) nr++;
fout<<nr;
fout.close();
return 0;
}

Problemă demonstrativă

În continuare vă voi prezenta o problemă de pe infoarena care se rezolvă cu ajutorul ciurului lui Eratostene.

Enunţ

Gheorghe a învățat la școală despre numere prime. A învățat că un număr este prim, dacă se divide doar cu 1 și cu el însuși(1 nu este considerat număr prim). A aflat că există algoritimi foarte eficienți care pot determina dacă un număr este prim sau nu, în timp chiar sub polinomial. Din păcate acești algoritmi sunt foarte complicați, și Gheorghe s-a gândit la o aproximare. Ideea lui este să consideri un număr prim dacă nu se divide la primele K numere prime.

Cerinţă

Demonstrează că ideea lui Gheorghe este doar o aproximare. Dându-se un număr K (1 ≤ K ≤ 100.000), află cel mai mic numar N care nu este divizibil cu primele K numere prime, dar nu este prim.

Date de intrare

Pe prima linie din fişierul prim.in se va afla numărul K.

Date de ieşire

Pe prima linie a fişierului prim.out se va gasi numarul N căutat.

Exemplu

Pentru valoarea 3 ca dată de intrare se va afișa 49, pentru că primele 3 numere prime sunt 2, 3, 5. Numerele care nu sunt divizibile cu 2, 3 sau 5 sunt : 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 49, .. 49 este cel mai mic numar care nu este prim.

Rezolvare

Deoarece nu știm de câte numere vom avea nevoie, am preferat să folosesc un define pentru 1.500.000, acest număr fiind „capătul” vectorului. Până acolo vom face parcurgerea vectorului, aplicând Ciurul lui Eratostene. Variabila nrp desemnează numărul de parcurgeri, astfel, când se ajunge la k+1 parcurgeri n va lua valoarea pătratului lui i, până atunci multiplii lui i fiind „eliminaţi”, valoarea lor din vector devenind 0. Condiția de la început  if(prim[i])  se asigură că se vor verifica doar numerele reale. Datorită faptului că pătratul unui număr prim nu se poate divide la numărul prim anterior, ne dăm seama că soluția i*i după k+1 parcurgeri este cea corectă.

Codul

#include <fstream>
#include <math.h>
#define INF 1500000

using namespace std;

bool prim[INF];

int main(){
ifstream fin("prim.in");
ofstream fout("prim.out");
long long n,k,nrp,i,j;
fin>>k;
for(i=2;i<INF;i++)
  prim[i]=1;
for(i=2,nrp=0;i<=INF;i++)
  if(prim[i]){
    if(++nrp==k+1){
      n=(long long)i*i;
      fout<<n;
      fout.close();
      return 0;
    }    
    for(j=i;j<=INF;j+=i)
      prim[j]=0;
  }
}

Sursa: Ciurul lui Eratostene. Problema demonstrativă.

Etichete: C++ciurEratosteneProbleme algoritmicăprobleme c++Tehnictutorial C#tutorial ciur

— Bogdan Condurache a scris 80 articole

Contact | bogdan@worldit.info | @bcman31 | WorldIT Mă numesc Bogdan Condurache şi sunt pasionat de informatică, în special de securitatea IT. Am experienţă în malware researching şi programare în diverse limbaje. Am reuşit să evoluez datorită WorldIT, mulţumită articolelor de calitate de pe acest blog, iar acum vreau să ajut la rândul meu. Dacă eşti de părere că poţi ajuta la dezvoltarea acestei comunităţi, nu ezita să o faci.

  • Articolul anterior Summify – Start-up-ul românesc este cumpărat de Twitter
  • Articolul următor Infografic de sâmbătă #11 – Luptele dintre gadget-uri

7 Comentarii

  1. dimitriepirghie spune:
    ianuarie 21, 2012 la 10:43 am

    Interesant, ar merge o problema si cu numerele extraprime 🙂

    • Andrei Avădănei spune:
      ianuarie 21, 2012 la 10:43 am

      Am retinut sugestia.

  2. happyday spune:
    ianuarie 21, 2012 la 4:59 pm

    m-a ciuruit asta micu ! 😀

  3. Nick (tatăl lui Gheo) spune:
    ianuarie 23, 2012 la 5:12 pm

    Nu-i mai rezolva tu problemele lui Gheo, lasă-l să învețe și singur, că așa se obișnuiește puturos! 😆

  4. Bogdan Condurache spune:
    ianuarie 23, 2012 la 5:57 pm

    @Tatăl nefericit: Păi nu i-am rezolvat problema. Eu doar i-am arătat că greșește. Mai departe se descurca singur 😀

  5. Nick (tatăl bucuros) spune:
    ianuarie 23, 2012 la 8:26 pm

    Ufff, mi-ai luat o piatră de pe suflet ! 😆

  6. STfebann spune:
    februarie 18, 2014 la 7:53 pm

    Problema e buna dar ce-i cu bool 😮


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • iunie 2022
    L Ma Mi J V S D
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Ciurul lui Eratostene – sursă + problemă rezolvată
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons