Keskustelu: Koodit: C: onko alkuluku

bool onkoAlkuluku(int luku);

palauttaa true jos int luku on alkuluku, muuten false.
tehty välitunnilla ilman kääntäjää, mutta pitäisi toimia.

edit. korjattu tuo kun ohjelma väitti ykköstä alkuluvuksi

bool onkoAlkuluku(int luku)
{
  int kasvata = 1,  jakaja = 2, jaannos;
  if(luku==1) return false;
  if(luku == 2) return true;
  do
    {
      jaannos = luku % jakaja;
      if(jaannos == 0)
        return false;
      jakaja += kasvata;
      kasvata = 2;
    } while(jakaja < luku/2);
  return true;
}

Muuten ihan toimiva, mutta tulos on väärinpäin. Eli tuo palauttaa false, jos luku on alkuluku.

tuo ehtolause oli väärin 'if(luku==2) return false;' nyt sekin on korjattu.
luuppi on palauttanut true alkuluvusta alusta pitäen.

Ykkönen EI ole alkuluku. Ymmärtääkseen tämän tulisi miettiä tarkemmin alkulukujen määritelmää. "Alkuluku on luku, jota ei voi jakaa muulla kuin yhdellä tai itsellään." Luvut yksi ja testattava luku itsessään muodostavat tavallaan yhden joukon, jolla jokainen luku voidaan jakaa. Kaikki muut luvut muodostavat toisen joukon. Nämä toisen joukon luvut ovat ne, joilla testattava luku koetetaan jakaa. Jos testataan esim. lukua 9, koetetaan jakaa se luvuilla 2, 3, 4, 5, 6, 7 ja 8. On turhaa kokeilla 4:llä, koska kokeiltiin jo 2:lla. Sitä paitsi 3 tuotti jo tulosta.

Muistaakseni Arkhimedes kehitti seuraavan algoritmin alkulukujen etsimiseen:

Ensimmäinen alkuluku on 2
Ensimmäinen kokeiltava luku on 3
Kokeile jakaa luku jokaisen aikaisemmin löydetyn alkuluvun kanssa.
Jos jakojäännös on 0, luku ei ole alkuluku, kokeile seuraavaa
Jos jakojäännös ei ole 0, kokeile jakoa seuraavalla löydetyllä alkuluvulla, kunnes jakajan neliö on suurempi kuin kokeiltava luku
Jos jakajan neliö on suurempi kuin kokeiltava luku, luku on alkuluku

Tästäkin pitäisi ilmetä, että alkulukujen sarja alkaa luvuilla 2, 3, 5, 7, 11, 13...
Jos se alkaisi ykkösellä, algoritmi ei toimi.

LIBCD.lib(crt0.obj) : error LNK2001: unresolved external symbol _main
Debug/alkuluku.exe : fatal error LNK1120: 1 unresolved externals
Error executing link.exe.

alkuluku.exe - 2 error(s), 0 warning(s)

monkkats; jos tuota suoraan tuosta yrität kääntää, niin linkkeri sanoo erroria, koska tuossa ei ole main -funktiota (pääohjelmaa)
tämä korjaa ongelman

#include <iostream>
bool onkoAlkuluku(int luku);
int main()
{
  cout << onkoAlkuluku(50) << endl;
  return 0;
}
// ja tähän alle yo. koodivinkki

Btw nopeuttaakseen tota niin:
while(jakaja < luku/2);
pitäisi katsoa onko jakaja vähemmän tai sama kuin annetun luvun neliöjuuri.

Tarkoitat varmaan sqrt(luku) eikä luku/2.

Kas, yli kaksi vuotta vanha keskustelu! No, ei se mitään...

while(jakaja < sqrt(luku));

toimii, mutta...

while(jakaja*jakaja < luku);

on nopeampi. Tai oikeastaan, koska jakaja muuttuu koko ajan, mutta luku pysyy samana, kannattaa se laskea vain kerran, eli juuri = sqrt(luku), sitten

while(jakaja < juuri);

tomaattigeeni kirjoitti:

(20.10.2003 17:16:21): monkkats; jos tuota suoraan tuosta yrität...

ei tämänkään kanssa kyllä toimi, herjaa tuota " cout << onkoAlkuluku(50) << endl;" riviä

Onpa sen verran epäselvä vinkki ja vanhentunutta kommentointiakin, että poistetaan ja tehdään uusi tilalle.