[C++] Program za iskanje praštevila

Pozdravljeni.

S pomočjo while zanke sem poskušal napisati program, ki bi preveril, ali je vneseno praštevilo res praštevilo ali ne. Program deluje vse lepo za cca. prvih 50 števil, naprej pa več ne.

Je kdo tako prijazen, da mi pove kje je napaka? Najlepša hvala.

http://prntscr.com/29nlh0

V glavnem ideja je pravilna? Ker nisem ravno najbolj prepričan, da razumem delovanje te while zanke.

Cout je izpis (standard output stream), cin je vpis (standard input stream).

Tvoj algoritem gre čez vsa števila manjša od vnesenega. V spremenljivko c dobiš zmnožek ostankov pri deljenju vnesenega števila z zaporednimi manjšimi števili.

Za 7:
c = 1*1*3*2*1; //dobiš število različno od 0

Če imaš število, ki ni praštevilo, se zgodi nekaj takega:
Za 6:
c = 0 * 0 * 2 * 1; //dobiš 0, ker je en (ali več) ostankov 0

Ampak če preverjaš za malo večje število, dobiš v spremenljivki c neko zelo zelo veliko število. Tako zelo veliko, da ga ne moreš več spravit v 32 bitov, kolikor prostora zavzema podatkovni tip int, zato se programu zmeša. Torej ideja je pravilna z matematičnega stališča, s praktičnega (delaš na računalniku, ki ne more hraniti poljubno velikih števil) pa ne.

Boljši pristop je, da namesto množenja ugotoviš, ali so bili vsi ostanki različni od nič, na kak drug način. Pred štartom while zanke lahko neko spremenljivko postaviš na true. Če naletiš na ničeln ostanek, jo nastaviš na false. Če je po izvedbi while zanke spremenljivka še vedno true, imaš praštevilo, v nasprotnem primeru pa ne.

Dve preprosti spremembi, pa bo delal tudi tale algoritem.

14: bool c = true;

Efekt je isti, kot ce vzames integerje: cim je eno stevilo deljitelj, bo c postal false, drugace pa ne. Ne bos pa prisel do integer overflowa.

17: while(c && k*k<n){

Ko enkrat najdes deljitelja, nima smisla nadaljevati, ker ves, da ni prastevilo. Dalj od korena stevila pa tudi nima smisla iskati, kajti, ce do tam ni bilo deljitelja, ga tudi kasneje ne bos nasel.

Hvala vsem za odgovore, sem že predvčeraj pogruntal, da namesto z množenjem enostavno pristopim s seštevanjem. Torej če definiram pred zanko vsoto int vsota = 0, v zanki pa enostavno napišem pogoj, torej če je ostanek pri deljenju danega števila enak 0 -> s=s+1.

Izven zanke sem nato dodal pogojni stavek, torej če je s>0, potem dano število ni praštevilo, else Je praštevilo.

Nisem se zavedal tega integer overflowa, ker je program iz matematičnega vidika bil korekten.

Tak da @drola hvala, da mi nisi takoj izdal rešitve, s tem da sem sam popravil program sem več odnesel kot sicer.

Lp