Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
Publicat la 20 martie 2020 · algoritmiolimpiadaclasa 9cpp
Să zicem că vrem să aflăm dacă mai multe numere sunt sau nu prime. Desigur, putem aplica algoritmul de aflare a numărului de divizori pentru toate numerele, doar că dacă avem foarte multe şi sunt şi foarte mari, va fi dificil să ne încadrăm în timp.
Din fericire, algoritmul Ciurului lui Eratostene este foarte util pentru a afla dacă orice număr mai mic decât un număr stabilit (de regulă 1.000.000) este sau nu prim.
Apar foarte des probleme cu Ciurul lui Eratostene.
ATENȚIE! Formulele nu trebuie reținute, ci deduse.
Începem de la 2 până la cel mai mare număr stabilit, să îl notăm MAX. Ştim că 2 este prim, aşadar toți multiplii lui 2 nu sunt, şi îi marcăm într-un vector ca fiind neprimi. Continuăm crescător (3, 4, ...) şi când întâlnim un nou număr prim (care n-a fost marcat anterior; adică care nu este multiplu de nici un alt număr mai mic decât el), marcăm din nou multiplii. O vizualizare foate clară, făcută de Wikipedia:
Implementarea algoritmului
int ciur[MAX + 1];
//semnificație//pentru mai multe detalii: https://100din100.netlify.app// ciur[i] = 0 atunci nr este prim//pentru mai multe detalii: https://100din100.netlify.app// ciur[i] = 1 atunci nr nu este prim//pentru mai multe detalii: https://100din100.netlify.appfor(int i = 2; i <= MAX; i++) {
if(ciur[i] == 0) { //numărul este prim//pentru mai multe detalii: https://100din100.netlify.app for(int j = 2 * i; j <= MAX; j = j + i) {
ciur[j] = 1;
}
}
}
După ce scriem ciurul, putem afla instant pentru orice număr 1 ≤ n ≤ MAX dacă este sau nu prim.
Cu ce ne mai ajută ciurul lui Eratostene?
Modificând un pic algoritmul, putem afla instant pentru orice număr numărul de divizori, suma lor, numărul de divizori primi, suma lor, indicatorul lui Euler şi multe altele. Iată câteva video tutoriale despre astea:
Numărul de divizori cu ciur
Pentru fiecare număr (începând de la 1!), incrementăm toate pozițiile multiplilor (1: 1, 2, 3, ...; 2: 2, 4, 6, ...; ...)
Algoritmul descris în video:
#include <iostream>
#define MAX 1000000
using namespace std;
///Se da un numar n si n numere naturale <= 1 000 000.//pentru mai multe detalii: https://100din100.netlify.app///Aflati pentru fiecare numarul de divizori.//pentru mai multe detalii: https://100din100.netlify.app///(n <= 1 000 000)//pentru mai multe detalii: https://100din100.netlify.app
int n, x, ciur[MAX + 1];
int main()
{
//1. Generare ciur//pentru mai multe detalii: https://100din100.netlify.app for(int i = 1; i <= MAX; i++)
for(int j = i; j <= MAX; j += i)
ciur[j]++;
//2. Citire n//pentru mai multe detalii: https://100din100.netlify.app cin>>n;
//3. Citire valori si afisare pentru fiecare//pentru mai multe detalii: https://100din100.netlify.app for(int i = 1; i <= n; i++) {
cin>>x;
cout<<x<<" are "<<ciur[x]<<" divizori.
";
}
return 0;
}
Suma divizorilor folosind ciurul
Pentru fiecare număr (începând de la 1!) îl adunăm la toți multiplii (pentru fiecare j, adunăm i).
Algoritmul descris în video:
#include <iostream>
#define MAX 1000000
using namespace std;
//Se da un numar n si n numere naturale <= 1 000 000.//pentru mai multe detalii: https://100din100.netlify.app//Aflati pentru fiecare suma divizorilor.//pentru mai multe detalii: https://100din100.netlify.app//(n <= 1 000 000)//pentru mai multe detalii: https://100din100.netlify.app
int n, x, ciur[MAX + 1];
int main()
{
//1. Generare ciur//pentru mai multe detalii: https://100din100.netlify.app for(int i = 1; i <= MAX; i++)
for(int j = i; j <= MAX; j += i)
ciur[j] += i; ///i este divizorul lui j; adunam la suma div lui j//pentru mai multe detalii: https://100din100.netlify.app//2. Citire n//pentru mai multe detalii: https://100din100.netlify.app cin>>n;
//3. Citire valori si afisare pentru fiecare//pentru mai multe detalii: https://100din100.netlify.app for(int i = 1; i <= n; i++) {
cin>>x;
cout<<x<<" are suma divizorilor egala cu "<<ciur[x]<<"
";
}
return 0;
}
Numărul de divizori primi cu ciur
Pentru fiecare număr prim (începem de la 2 şi numerele prime sunt numerele care nu au până acum divizori), incrementăm ciurul pentru toți multiplii.
Algoritmul descris în video:
#include <iostream>
#define MAX 1000000
using namespace std;
//Se da un numar n si n numere naturale <= 1 000 000.//pentru mai multe detalii: https://100din100.netlify.app//Aflati pentru fiecare numarul divizorilor primi.//pentru mai multe detalii: https://100din100.netlify.app//(n <= 1 000 000)//pentru mai multe detalii: https://100din100.netlify.app
int n, x, ciur[MAX + 1];
int main()
{
//1. Generare ciur: atentie, contorizam doar divizorii primi!//pentru mai multe detalii: https://100din100.netlify.app for(int i = 2; i <= MAX; i++) {
if(!ciur[i]) {
for(int j = i; j <= MAX; j += i)
ciur[j]++;
}
}
//2. Citire n//pentru mai multe detalii: https://100din100.netlify.app cin>>n;
//3. Citire valori si afisare pentru fiecare//pentru mai multe detalii: https://100din100.netlify.app for(int i = 1; i <= n; i++) {
cin>>x;
cout<<x<<" are "<<ciur[x]<<" divizori primi.
";
}
return 0;
}
Test din Ciurul lui Eratostene
Completează următoarea secvență de cod:
//Până unde putem merge cu ciurul? int ciur[1001]; for(int i = 2; i <= ; i++) { //algoritm ciur }
· Vezi răspunsul
//pentru mai multe detalii: https://100din100.netlify.app
Primul tau program, variabile si operatii - TUTORIAL COMPLET C++
Eşti elev de liceu şi nu înțelegi informatica? Acest clip ar trebui să te ajute să înțelegi cele mai elementare aspecte privind informatica de liceu - algoritmica...
Problemele de informatică pot fi dificile uneori, şi este util să vedem o soluție bună pentru a ne autoverifica. De multe ori sunt necesare doar nişte modificări minore, de aceea este bine să analizăm soluțiile bune cu atenție!
Video - Probleme Rezolvate PbInfo
Aici gasiti rezolvarea mai multor probleme de pe site-ul pbinfo.ro, în format video, pe canalul nostru de YouTube.
De ce avem nevoie de date?
În timp ce lucrăm cu valori, avem nevoie (uneori chiar suntem siliți!) să memorăm datele undeva, în memorie. Prin intermediul variabilelor putem accesa o zonă de …
Ce este Şmenul lui Mars?
Să zicem că avem un şir a[] cu n elemente. Unele probleme cer efectuarea unor operații de tipul sum(st, dr, val), cu semnificația că adunăm la …
Ce este căutarea binară?
Să zicem că ai un vector a[] cu n elemente crescătoare. Căutarea binară este un algoritm eficient care determină dacă orice număr x apare sau n…
Prezentul articol te va ajuta să îndeplineşti diferite aplicații cu divizorii unui număr.
Trebuie cunoscută parcurgerea divizorilor unui număr, înainte de toate, ca să ne asigurăm că ştim s…
Afişare cu 2 zecimale exacte, fără şi cu rotunjire - TUTORIAL C++
Tutorialul acesta te învață cum să afişezi un număr real cu mai multe zecimale exacte. Multe probleme cer...
Algoritmi elementari - video
Tutoriale uşor de urmărit, sub forma unor videoclipuri!
Sortarea în informatică reprezintă procesul de a ordona un şir de obiecte (numere, caractere, sau chiar şiruri) după un anumit criteriu.
Spre exemplu, putem ordona crescător sau descrescăto…
Cu ce ne ajută sumele parțiale?
Unele probleme cer aflarea sumei elementelor unei secvențe dintr-un şir dat. Metoda naivă, care face suma tuturor elementelor din secvența cerută, deobicei n…
Să zicem că vrem să aflăm dacă mai multe numere sunt sau nu prime. Desigur, putem aplica algoritmul de aflare a numărului de divizori pentru toate numerele, doar că dacă avem foarte multe şi sun…
De ce citirea din fişier?
De multe ori este necesară citirea şi afişarea în fişier, unul din motive fiind faptul că nu trebuie să reintroducem datele de intrare de fiecare dată când rulăm p…
Un număr de forma b la puterea e nu poate fi calculat precum celelalte operații (adunarea, scăderea, înmulțirea, împărțirea) pur şi simplu. În articolul acesta vom prezenta un mod foarte …
Care-i faza?
În aceste câteva tutoriale vom învăța cum să îți creezi propriul joc video în Python. Puteți viziona atât pe YouTube, cât şi în format text pe site-ul nostru (aici adică).
…
Dându-se o dată (zi lună an), trebuie verificat dacă data este validă sau nu.
Exemplu:Intrare
zi = 3, luna = 4, an = 2021
Ieşire
DA
Pentru a verifica da…
Ce este tabelul ASCII?
Calculatorul reține numere (valori de 1 şi de 0), aşadar a fost nevoie de o corespondență între numere şi caractere pentru a putea reprezenta litere, si…
Acest articol urmăreşte aplicarea diferitelor aplicații cu cifrele unui număr: suma cifrelor, numărul de cifre, oglinditul unui număr ş.a.m.d. Puteți găsi multe probleme care cer prelucrarea cif…
Ce este un vector de frecvență sau un vector caracteristic?
Vectorii caracteristici rețin dacă un element se află într-un vector sau nu. Similar, vectorii de frecvență rețin numărul de apar…
Alcătuirea unui program pentru rezolvarea unei probleme se rezumă defapt la rezolvarea unor probleme mai mici. Spre exemplu, pentru a afla suma numerelor prime dintr-un şir, trebuie să ştim cum …
Cu ce ne ajută parcurgerea matricei pătratice în spirală?
În concursuri şi olimpiade apar probleme legate de parcurgerea matricei în spirală. Deşi ideea de bază este destul de uşoară, algor…
Ce este coada?
Coada (Queue din engleză) este o structură de date liniară care funcționează prin inserarea elementelor noi la spate şi prin eliminarea elementelor doar prin față. Altfel spu…
Dându-se un şir de numere naturale distincte, aflați al doilea cel mai mic număr din şir.
Exemplu:Intrare
9 5 8 2 4
Ieşire
4
Explicație4 este al doilea cel mai mi…
Învață să programezi gratis!
Am lansat InfoAs, o platformă de informatică cu sute de probleme, lecții și concursuri, totul gratuit. Încearcă acum!
