Question

Am doua intrebari:
1)Care este algoritmul pentru numere prime in C++
2)Cum se rezolva asta :Cerința
Se dă o matrice cu n linii și m coloane și elemente numere naturale. Să se determine câte dintre elementele situate pe linii cu indici pari sunt prime.

Date de intrare
Programul citește de la tastatură numerele n m, iar apoi n șiruri cu câte m numere naturale, reprezentând elementele matricei.

Date de ieșire
Programul va afișa pe ecran numărul C, reprezentând valoarea căutată.

Restricții și precizări
1 ≤ n , m ≤ 100
elementele matricei sunt numere naturale mai mici decât 1.000.000
liniile matricei sunt numerotate de 1 la n, iar coloanele de la 1 la m

Answer 1

Un nr este prim daca este divizibil doar cu 1 sau el insusi.
Deci este usor sa demonstrezi ca un nr nu este prim: gasesti un divizor diferit de catre cele 2 valori. Sa zicem ca acel nr este notat cu x
Deci poti sa faci un algoritm prin care presupui initial ca este prim, apoi cauti prin toate numerele de la 2 la x-1 ca sa gasesti un divizor. Daca exista, nr nu este prim

Deja vedem prima optimizare pe care o putem face. Cel mai mic divizor pe care un numar x poate il avea diferit de 1 este 2, atunci cel mai mare divizor pe care il poate avea este x/2. De exemplu, pentru x=64, nu are rost sa cauta de la 2 la 63, ar fi suficient sa cautam de la 2 la 32
Dar apoi daca observi, toti divizorii apar in perechi, si tu trebuie sa gasesti valoarea inferioara a perechii. ai (2,32) (4,16) (8,8) dar pe tine te intereseaza sa gasesti doar valoarea 2,4 sau 8 ca sa demonstrezi ca nu este prim.
Toti acesti divizori inferiori apar in intervalul 2 pana la radical(x), pentru ca radicalul este clar cea mai mare valoare inferioara, din moment ce divizorul pereche este tot radicalul.

In cazul lui 64, nu pare de mare ajutor pentru ca primul divizor este 2, deci e clar ca nu e prim. Vei ajunge la valoarea radical(x) doar in cazul numerelor care sunt patrate perfecte de alte numere prime. De exemplu pentru x=25=5*5, nu vei gasi alt divizor pana la 5.

Aceasta este o functie care iti rezolva problema
int prim(int x){
//este_prim este ceea ce returneaza functia
//initial presupunem ca este prim, apoi verificam daca este asa
//si ii dam valoarea 0 daca are un divizor propriu
int i,este_prim=1;
for(i=2;i<=sqrt(x);i++){
//verificam daca x se imparte la un divizor i
//asta ne dam seama prin faptul ca restul impartirii este 0
if(x%i==0){
//daca am gasit un divizor propriu, atunci nu mai este prim
este_prim=0;
//iesim din loop
break;
}
}
//daca in urma recursivitatii este_prim nu este niciodata schimbat de la 1 la 0
//inseamna ca nr e prim, altfel nu este prim
return este_prim;
}

2) Pentru a rezolva problema, o data avuta functia de mai sus, trebuie sa verifici doar ca functia returneaza valoarea 1. Pentru a verifica asta doar pe elementele de pe linii pare, vei parcurge matricea pe linii incepand cu indicele i=2, apoi sari din 2 in 2(i=4,i=6..) cat timp i este mai mic sau egal decat n, nr total de linii.
Implementarea completa este mai jos:
#include <iostream>
#include <cmath>
using namespace std;
//Functia verifica daca un numar este prim sau nu
//daca este prim returneaza 1, altfel 0
int prim(int x){
//este_prim este ceea ce returneaza functia
//initial presupunem ca este prim, apoi verificam daca este asa
//si ii dam valoarea 0 daca are un divizor propriu
int i,este_prim=1;
for(i=2;i<=sqrt(x);i++){
//verificam daca x se imparte la un divizor i
//asta ne dam seama prin faptul ca restul impartirii este 0
if(x%i==0){
//daca am gasit un divizor propriu, atunci nu mai este prim
este_prim=0;
//iesim din loop
break;
}
}
//daca in urma recursivitatii este_prim nu este niciodata schimbat de la 1 la 0
//inseamna ca nr e prim, altfel nu este prim
return este_prim;
}

int main(){
//in dimensiunile matricii pun 100 de elemente pentru ca asta e restrictia din cerinta
//tipul de date declarate este int: este un tip de data pe 32 biti
//deci este suficient sa tina numere intregi de pana la un milion
int a[100][100],m,n,i,j,C=0;
cout<<"Introduceti dimensiunile matricii:";
cin>>n>>m;
cout<<"Introduceti elementele matricii:\n";
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
}
}
//incepem iteratia de pe linii cu linia a doua si apoi tot adaugam
for(i=2;i<=n;i=i+2){
for(j=1;j<=m;j++){
//daca nr este prim
if(prim(a[i][j])==1){
cout<<a[i][j]<<" ";
//incrementam counterul de elemente prime
C++;
}
}
}
cout<<C;
return 0;
}