Keskustelu: Koodit: C++: Alkulukujen laskentaa C++

poistettu huonona

Mitenniin 2 ei ole alkuluku?

2 on alkuluku.

0 ja 1 eivät ole. 2 on.

Juu... huomasin sen.

Päivitin uuden version, joka ei ole aivan niin tyhmä kuin ensimmäinen versio, ja nopeus moninkertaistui.

Nopeudeltaan ei kyllä ole vieläkään kovin hyvä...

toi olisi nopeampi jos se kertoisi aina ~1000 luvun välein että montako on löydetty, ja heittäisi kaikki tiedostoon... mä tein yhden sillä tavalla.

Päivitin taas uuden versio, suurin uudistus on että kertoo kauanko laskentaan kului. Myös tiedostonkäsittelyä mukana.

Ei tätä näin kannata tehdä. Aikaa vievä algoritmi ja muutenkin on suositeltavaa käyttää assosiatiivista säiliötä eli std::set, ja käyttää jotain tunnettua ja nopeahkoa seulaa, esmes Eratostheneen.

Voisit myös korvata stdio.h ja time.h -> cstdio ja ctime

Olisiko tuosta korvaamisesta käytännön hyötyä?

Noniin.. otin käyttöön noi cstdio ja ctime -kirjastot.

lainaus:

for (jaetaa=3; jaetaa<=mahdollinen/2; jaetaa++)

Ilmeisesti algoritmisi yrittää jakaa luvuilla 3, 4, 5, 6, 7, 8, 9...
Oliko se Arkhimedes vai Eratosthenes joka keksi, että pitää kokeilla jakaa luvuilla 2, 3, 5, 7, 11, 13, eli jo löydetyillä alkuluvuilla. Toi sun for-silmukkasi voisi siten olla jotenkin näin:

for (i = 0; alkuluku[i]*alkuluku[i] < mahdollinen; i++)

...eli käytät alkuluku-taulukkoa huolimatta siitä, tulostatko tiedostoon vai ei. Lisäät taulukkoon kaikki löydetyt alkuluvut ja käytät niitä jakajina, kun kokeilet seuraavaa mahdollista.

Ja kokeilu voidaan päättää, kun jakajan neliö >= mahdollinen. Esim kun tutkit lukua 127, eikä jako 12:lla (tai sitä pienemmillä) onnistu, sinun ei tarvitse jatkaa 64:ään asti. 12*12 = 144, mikään suurempi luku kuin 12 ei voi jakaa 127:ää, koska silloinhan olisit jo löytänyt sen. Veikkaan että tämä on nopein mahdollinen algoritmi. Se tosin vaatii aina sen, että etsitään kaikki alkuluvut kakkosesta alkaen.

Voi pehveli! En hallitse tätä sivustoa, olisi pitänyt panna jotain kooditageja tuonne. Käytin muuttujaa i ja panin sen hakasulkuihin, jolloin teksti muuttui kursiiviksi. Onkohan tämä oikeamman näköistä:

for (j = 0; alkuluku[j]*alkuluku[j] < mahdollinen; j++)

miks toi loppuu kun kaikki on löydetty?

1 - 10 menee aika kauan ... kokeiliko joku käyttää maksimilukua? kuinka kauan kesti?

Alkulukujahan on loputtomiin. Jos sen muuten tekee sillä periaatteella, että jaetaan jo löydetyillä alkuluvuillahan niin sittenhän ohjelma käy koko ajan sitä hitaammaksi, mitä enemmän on löydetty, koska mitä enemmän on löydetty, sitä kaueamman kestää jakaa. Ainakin tein kerran itse sellainen QB:llä ja oli tietysti paljon hitaampi.

Vielä kauemmin kestää jakaa kaikilla kokonaisluvuilla. Jos lukusi on 221, kumpi on nopeampaa? Koettaa jakaa luvuilla 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ja 13 vai luvuilla 2, 3, 5, 7, 11 ja 13? Jos ei voi jakaa 3:lla, ei voi myöskään jakaa 6:lla eikä 9:llä. Näin se vain on.

lainaus:

miks toi loppuu kun kaikki on löydetty?

taas unohtu system("PAUSE").

ilman niitä ei mun mielestä toimi devillä

Ohjelman on tarkoituskin sammua kun laskenta tulee valmiiksi. Tiedot laskennasta tulevat tekstitiedostoon joka ilmestyy exen kanssa samaan hakemistoon.

Btw nopeuttaakseen tota niin kannattaisi tarkistaa onko jakaja vähemmän tai sama kuin annetun luvun neliöjuuri.