Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: numere prime  (Citit de 9273 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
contesSa_girL
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« : 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
Memorat
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #1 : Septembrie 25, 2008, 18:57:44 »

Vezi inceputul articolului asta: http://infoarena.ro/ciurul-lui-eratostene
« Ultima modificare: Decembrie 16, 2008, 08:32:15 de către Andrei Grigorean » Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #2 : 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;
}
« Ultima modificare: Septembrie 27, 2008, 19:20:24 de către Bitis Gabriel » Memorat
miculprogramator
Nu mai tace
*****

Karma: 65
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #3 : 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.... Eh?
« Ultima modificare: Ianuarie 18, 2009, 12:04:20 de către miculprogramator » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #4 : 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
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #5 : 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.
Memorat
miculprogramator
Nu mai tace
*****

Karma: 65
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #6 : Ianuarie 18, 2009, 12:30:24 »

deci o iei de la 2 da, asa-i...nu mi-am dat seama Smile
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #7 : 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.
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #8 : 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 Smile
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #9 : Decembrie 27, 2009, 16:27:28 »

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 Smile
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
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #10 : Decembrie 27, 2009, 20:22:35 »

Tie ce complexitate ti se pare ca am eu ?
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines