shanker'

Un număr prim este un număr care nu se împarte la nici un alt numar, cu excepția cifrei 1 și el însuși. Deci ce putem deduce din asta? Un număr prim: trebuie să aibă obligatoriu 2 divizori. nu se împarte niciodată la 2, deci nu este număr par. nu este mai mic decât 2, deci un număr negativ nu poate fi număr prim. singurul număr par care este număr prim, este cifra 2. Cel mai simplu algoritm pentru a afla dacă un numar este sau nu prim: int main() { int N; cin >> N; bool Prim = true; for (int i=2; i<N; i++) if (N % i == 0) Prim = false; if (Prim) cout << "Este Prim"; else cout << "Nu este prim"; } Însă, aceasta poate fi optimizată în felul următor: int main() { int N; cin >> N; // bool este o variabila booleana care poate fi ori adevarata, ori falsa // presupunem ca numarul nostru este un numar prim bool Prim = true; // incepem de la 2 pana la patratul contorului // aceasta functie verifica fiecare numar din intervalul [2, sqrt(N)] for (int i=2; (i*i)<=N; i++) { if (N % i == 0) Prim = false; } // in cazul in care conditia din bula nu a fost indeplinita, atunci numarul nostru este prim if (Prim) cout << "Este prim"; else cout << "Nu este prim"; } Acum că știm să aflăm dacă un număr este sau nu prim, mai rămâne să facem un program care ne arată suma tuturor numerelor prime pana la N. Cea mai simplă metodă, însă foarte slabă, mai ales pentru numerele foarte mari, ocupând chiar și de 200 de ori mai mult timp decât varianta optimizată, este următoarea funcție: int main() { int N, Suma = 0; cin >> N; // Vom declara variabila booleana in afara bulei bool Prime; cout << "Numerele prime sunt: "; // Cum 1 nu este numar prim, vom incepe direct de la 2 for (int i=2; i<=N; i++) { Prime = true; // Consideram ca i este un numar prim // Aici obligatoriu trebuie ca variabila j sa fie mai mica decat i // De ce? // Sa zicem ca i = 15, daca j ajunge la 15, atunci 15:15 = 1 ==> variabila booleana va fi falsa // Stim ca un numar prim are voie sa se imparte chiar si la el insusi, dar el nu trebuie sa se imparta la numerele din intervalul [2,N-1] for (int j=2; j<i; j++) if (i % j == 0) Prime = false; // Daca i este prim, atunci il vom afisa si aduna in acelasi timp if (Prime) { cout << i << " "; Suma += i; } } cout << "\nSuma numerelor prime este: " << Suma; } Cu această funcție mi-a luat 5,11 secunde să calculez numerele prime până la 50,000. Varianta optimizată a acestei funcții este puțin mai delicată: #include <iostream> using namespace std; int PrimeVerif(int X); int main() { int N, Suma = 0; cin >> N; cout << "Numerele prime sunt: "; for (int i=1; i<=N; i++) { // Apelam functia ce verifica daca numarul este sau nu prim if (PrimeVerif(i)) { cout << i << " "; Suma += i; } } cout << "\nSuma numerelor prime este: " << Suma; } int PrimeVerif(int X) { // X este singurul numar par care este prim if (X == 2) return true; // 1 sau numerele negative, cat si cele pare, nu sunt prime if (X < 2 || X % 2 == 0) return false; // deoarece am eliminat din start faptul ca nu este numar par (deci nu se imparte la 2), vom verifica doar numerele impare cu o incrementare din 2 in 2 // obligatoriu trebuie sa punem patratul contorului mai mic sau egal decat X pentru a scapa de patratele perfecte for (int i=3; (i*i)<=X; i+=2) { if (X % i == 0) return false; } // dupa ce bula de sus a fost terminata, iar daca functia noastra ajunge sa citeasca aceasta linie, inseamna ca numarul nostru este numar prim return true; } Cu această funcție, calculul numerelor prime până la 50,000 a durat 1,5 secunde. A fost de aproximativ 3 ori mai rapidă decât funcția de mai sus.

@TLG RatoN, Uite aici o problemă similară cu ce cauți tu: https://www.pbinfo.ro/?pagina=probleme&id=2299

@FnZ https://www.pbinfo.ro/?pagina=probleme&id=3015 Știi s-o faci? Mai jos am făcut același lucru, însă nu-mi pot da seama ce rost are prima variabilă citită din enunț, așa că am sărit peste ea. Probabil de aia primesc doar 10 puncte? https://pastebin.com/mAfBtS9X

sau ... varianta cu un sunet mult mai bun,

Am renunțat la bubbleSort, în schimb folosind funcția sort din <algorithm> 100 de puncte gratuite here they are! #include <fstream> #include <algorithm> using namespace std; void Conditia_1(int Array[], int X, ofstream &WriteToFile) { for (int i=0; i<X; i++) { WriteToFile << Array[i] << " "; } } void Conditia_2(int Array[], int X, ofstream &WriteToFile) { WriteToFile << "\n"; for (int i=0; i<X; i++) { if (i == 0) { WriteToFile << "0" << " "; continue; } if (i == X) { WriteToFile << "0" << " "; break; } if ((float)(Array[i-1] + Array[i+1])/2 == Array[i]) { WriteToFile << "1" << " "; } else { WriteToFile << "0" << " "; } } } void printArray(int Array[], int X, ofstream &WriteToFile, void (*calledFunc)(int [], int, ofstream &)) { return (*calledFunc)(Array, X, WriteToFile); } int main() { ifstream ReadFromFile ("arhitectura2.in"); ofstream WriteToFile ("arhitectura2.out"); long long int X, Numar; ReadFromFile >> X; int Array[X]; for (int i=0; i<X; i++) { ReadFromFile >> Numar; Array[i] = Numar; } sort (Array, Array+X, greater<int>()); (*printArray)(Array, X, WriteToFile, Conditia_1); (*printArray)(Array, X, WriteToFile, Conditia_2); ReadFromFile.close(); WriteToFile.close(); }

E cineva pe aici ce rezolvă probleme pe pbinfo când plictiseala îl depășește? PM privat atunci A reușit cineva să obțină 100 de puncte la problema https://www.pbinfo.ro/?pagina=probleme&id=1192 ? Am creat următoarea chinezărie, însă chiar nu-mi pot da seama cum altcumva să rezolv problema pt. a „optimiza” programul (Apelurile de functii sunt 0, deci nu contează că am creat multe funcții) @FnZ, mi silă să-ți dau PM. Ce zici? Sau esti Mate-Info dgb? 😆 #include <iostream> #include <fstream> using namespace std; void swap(int *X, int *Y) { int Temp = *X; *X = *Y; *Y = Temp; } void bubbleSort(int Array[], int X) { for (int i=0; i<X; i++) { for (int j=0; j<X-i-1; j++) { if (Array[j] < Array[j+1]) swap(&Array[j], &Array[j+1]); } } } void Conditia_1(int Array[], int X, ofstream &WriteToFile) { for (int i=0; i<X; i++) { WriteToFile << Array[i] << " "; cout << Array[i] << " "; } } void Conditia_2(int Array[], int X, ofstream &WriteToFile) { cout << endl; WriteToFile << endl; for (int i=0; i<X; i++) { if (i == 0) { cout << "0" << " "; WriteToFile << "0" << " "; continue; } if (i == X) { cout << "0" << " "; WriteToFile << "0" << " "; break; } if ((float)(Array[i-1] + Array[i+1])/2 == Array[i]) { WriteToFile << "1" << " "; cout << "1" << " "; } else { WriteToFile << "0" << " "; cout << "0" << " "; } } } void printArray(int Array[], int X, ofstream &WriteToFile, void (*calledFunc)(int [], int, ofstream &)) { return (*calledFunc)(Array, X, WriteToFile); } int main() { ifstream ReadFromFile ("arhitectura2.in"); ofstream WriteToFile ("arhitectura2.out"); long long int X, Numar; // cin >> X; ReadFromFile >> X; int Array[X]; for (int i=0; i<X; i++) { // cin >> Numar; ReadFromFile >> Numar; Array[i] = Numar; } bubbleSort(Array, X); (*printArray)(Array, X, WriteToFile, Conditia_1); (*printArray)(Array, X, WriteToFile, Conditia_2); ReadFromFile.close(); WriteToFile.close(); }

Au dat faliment producătorii 😅