Imprimă pagina - numere prime

Titlul: numere prime
Scris de: stefania din Septembrie 25, 2008, 18:28:59

Este dat un nr n. Sa se verifice daca este prim.......va rog cine poate sa ma ajute...am nevoie urgent de ea

Titlul: Răspuns: numere prime
Scris de: Stefan Istrate din Septembrie 25, 2008, 18:57:44

Vezi inceputul articolului asta: http://infoarena.ro/ciurul-lui-eratostene

Titlul: Răspuns: numere prime
Scris de: Gabriel Bitis din Septembrie 25, 2008, 19:47:06

Folosind mai putina memorie, clasica verificare in O(sqrt(n)):

Cod:

int prim(int x)
{
   if (x == 1) return 0;
   if (x == 2) return 1;
   if (x % 2 == 0) return 0
   for (int i = 3; i * i <= x; i += 2) if (x % i == 0) return 0;
   return 1;
}

Titlul: Răspuns: numere prime
Scris de: A Cosmina - vechi din Ianuarie 18, 2009, 10:37:14

sau mai merge sa iei o variabila de tip boolean si....sa iti dau un exemplu
avem nr 8 , n=8
g(variabila boolean)=true {plecam de la premiza asta, ca 8 e nr pri}
impartim pe 8 la 2->>8/2=4
apoi de la 4 in jos impartim pe 8 la toate numerle (mai mici ca 8 sau mai mici sau egale cu 4):
8 MOD 1<>0->>g:=false;

LE: ai dreptate, mie mi s-a explicat cu nr mai mari de n/2...probabil ca nu era atenta profa, insa nici tu nu prea ai dreptate ca asa daca ei orice nr 10 de ex si il imparti la 1 iti sa din start ca nu-i prim , sau 2.... :-s

Titlul: Răspuns: numere prime
Scris de: Savin Tiberiu din Ianuarie 18, 2009, 11:08:48

tre sa incerci toate numerele mai mici ca N/2 nu mai mari.
Pentru 9 tie iti da ca e prim. E mai bine ce zice gabitzish

Titlul: Răspuns: numere prime
Scris de: Sima Cotizo din Ianuarie 18, 2009, 12:22:43

Citat

de ex si il imparti la 1 iti sa din start ca nu-i prim

D-aia niciodata nu imparti la 1.

Titlul: Răspuns: numere prime
Scris de: A Cosmina - vechi din Ianuarie 18, 2009, 12:30:24

deci o iei de la 2 da, asa-i...nu mi-am dat seama :)

Titlul: Răspuns: numere prime
Scris de: alexandru din Ianuarie 18, 2009, 12:51:08

Hm poate vi se pare interesant si foarte folositor:
http://forum.softpedia.com/index.php?act=attach&type=post&id=312561.

Titlul: Răspuns: numere prime
Scris de: Gabriel Bitis din Ianuarie 18, 2009, 12:53:01

Sa explic exact ce am facut acolo:

daca numarul e 1, nu e prim (1 nu e considerat numar prim)
daca numarul e 2, e prim
daca numarul e par si n'am iesit pe varianta cu 2, inseamna ca nu e prim (2 e singurul numar prim par)
verific pe rand toate numerele impare >= 3 si <= sqrt(x), daca sunt sau nu divizori ai lui x.

daca a trecut de toate verificarile astea, numarul e prim :)

Titlul: Răspuns: numere prime
Scris de: Simoiu Robert din Decembrie 27, 2009, 16:27:28

Citat din mesajul lui: Gabriel Bitis din Ianuarie 18, 2009, 12:53:01

Sa explic exact ce am facut acolo:

daca numarul e 1, nu e prim (1 nu e considerat numar prim)
daca numarul e 2, e prim
daca numarul e par si n'am iesit pe varianta cu 2, inseamna ca nu e prim (2 e singurul numar prim par)
verific pe rand toate numerele impare >= 3 si <= sqrt(x), daca sunt sau nu divizori ai lui x.

daca a trecut de toate verificarile astea, numarul e prim :)

Sunt de acord, dar la ultima verificare, nu poti face cu ciurul lui eratostene, imbunatatit, iti iasa un timp mult mai scurt, O(sqrt(n)), mai mutle detalii http://infoarena.ro/ciurul-lui-eratostene (http://infoarena.ro/ciurul-lui-eratostene)

Titlul: Răspuns: numere prime
Scris de: Gabriel Bitis din Decembrie 27, 2009, 20:22:35

Tie ce complexitate ti se pare ca am eu ?

infoarena

infoarena - concursuri, probleme, evaluator, articole => Teme => Subiect creat de: stefania din Septembrie 25, 2008, 18:28:59