Jaollisuus

Seuraa 
Viestejä119
Liittynyt10.12.2006

Millä tämän luvun voi jakaa 94683107 ilman jakojäännöstä?
Mitkä ovat luvun tekijät suppeimmassa muodossa?

Kirjoita nimesi vetoomukseen eläinoikeusjulistuksen puolesta osoitteeseen http://animalsmatter.org

Sivut

Kommentit (17)

Vierailija
KBolt
1, 1901, 49807



Ja sama litania vielä negatiivisena (-1, -1901 ja -49807).

Jos kanoonista muotoa ei itse viitsi alkaa isohkolle luvulle pähkäilemään, niin kannattaa laittaa tietokone miettimään. Pikagooglauksella löytyi ainakin tällainen apuväline.

Vierailija

Helppoja sääntöjähän jaollisuussäännöt on. Ne vaan unohtuu helposti jos ei tarvitse käyttää.

- Jos luvun viimeinen numero on parillinen niin luku on 2 jaollinen
- jos luvussa olevien numeroiden summa on kolmella jaollinen niin myös itse luku on
- Jos luvun kahden viimeisen numeron muodostama luku on jaollinen neljällä niin myös itse luku on
- Jos luvun viimeinen numero on 5 tai 0 niin luku on jaollinen viidellä
- Jos numero on jaollinen sekä kahdella että kolmella niin se on jaollinen myös luvulla 6
- Kerrotaan luvun viimeinen numero kahdella ja vähennetään tulos luvusta. Jos näin saatu luku on jaollinen luvulla 7, nolla mukaan lukien, niin myös alkuperäinen luku on
- Jos luvussa olevien kolmen viimeisen numeron muodostama luku on jaollinen kahdeksalla niin myös itse luku on
- Jos luvussa olevien numeroiden summa on jaollinen luvulla 9 niin myös itse luku on
- Vuorotellen lisätään ja vähennetään luvun numerot vasemmalta alkaen siten että alkuun lisätään nolla.
Esim. kyseinen luku 94683107 johon lisätään nolla
--> 094683107 --> 0+9-4+6-8+3-1+0-7 = -2
Jos tulokseksi tulee nolla niin luku on jaollinen 11:ta.
(kyseinen luku siis ei ole..)

Noilla pääsee jo alkuun. Loput pitää soveltaa...

Vierailija

Noista jaollisuussäännöistä ei vaan kauhean pitkälle ole apua, jos annettu luku on valittu riittävän hankalaksi. Ainakaan itse en viitsisi käsin alkaa pohtimaan, mikähän mahtaisi olla esimerkiksi luvun 493984863728044433 alkulukuhajotelma.

Tuo esimerkkiluku on vielä sen verran pieni, että kanooninen esitys löytyy nopeasti. Jos sen sijaan valittaisiin kaksi suurta alkulukua p ja q (molemmat esimerkiksi suuruusluokkaa 10^100), jotka eivät ole kovin lähekkäin toisiaan, niin tulon pq hajottaminen alkulukutekijöihin taitaisi olla jo melko työlästä.

Vierailija

Kyllähän se onkin työlästä mutta tuon suuruisia lukuja ei reaalielämässä tarvitse pilkkoakaan. Pienempiä kyllä.

Kun valitaan tarpeeksi suuria lukuja niin mikä tahansa matemaattinen lukujen manipulointi (jopa laskimella ja paperilla) on ihmiselle työlästä.
Jos taas pysytään maan pinnalla ja hyödyllisissä mittasuhteissa niin säännöistä on suuri apu.

Jos jostain kumman syystä joskus tarvitsee todella suuria lukuja käsitellä niin teen probleemasta ohjelmanpätkän jolla homma hoituu nopeasti. Helppoa mutta yksinkertaista.
Yksinkertaisista operaatioista selviää jo taulukkolaskennalla jos tietää mitä tekee.

Vierailija
KBolt
Jos jostain kumman syystä joskus tarvitsee todella suuria lukuja käsitellä niin teen probleemasta ohjelmanpätkän jolla homma hoituu nopeasti. Helppoa mutta yksinkertaista. Yksinkertaisista operaatioista selviää jo taulukkolaskennalla jos tietää mitä tekee.

Nyt taidat yliarvioida ohjelmointitaitojasi ja/tai aliarvioida ongelman haastavuutta. Jos todella osaisit kehittää nopean tekijöihinjakoalgoritmin, niin saisit luultavasti Fieldsin mitalin ja samalla mullistaisit koko kryptografian.

Vierailija

Öööö...nyt taidat yliarvioida oman kykysi lukea ja ymmärtää sekä tehdä päätelmiä.

Kyllähän se onkin työlästä mutta tuon suuruisia lukuja ei reaalielämässä tarvitse pilkkoakaan. Pienempiä kyllä.



Lue linkistäsi kohta "Special-purpose" ja "General-purpose"

Enhän minä maailmankaikkeuden ongelmaa ole väittänyt ratkaisseeni.
Olen hyvin tietoinen tehtävän vaikeudesta koska ensimmäisen kerran painin kyseisen asian kanssa jo vuonna -87. Silloin yksinkertaisen algoritmin ajo suht pienillä luvuilla kesti viikkoja.

Vierailija

Ihan mielenkiinnosta kokeilin omaa algoritmia VB:llä ja tuon ekan luvun 94683107 tekijät löytyi alle 0,3 ms. Tosin kovin isoja lukuja ei voi käyttää (Long-tyyppi ja Mod-funktio rajoittaa). Ei tämä toosakaan mikään huippunopea ole. Luvulla 493984863 meni 0,53 ms.

Vierailija
korant
Ihan mielenkiinnosta kokeilin omaa algoritmia VB:llä ja tuon ekan luvun 94683107 tekijät löytyi alle 0,3 ms. Tosin kovin isoja lukuja ei voi käyttää (Long-tyyppi ja Mod-funktio rajoittaa). Ei tämä toosakaan mikään huippunopea ole. Luvulla 493984863 meni 0,53 ms.



Tee seuraavaksi oma kirjasto suurien kokonaislukujen käsittelemiseen ja jaa tekiöihin vaikka kahden 50 merkkisen alkuluvun tulo Pian voi pian ruveta mittaamaan aikaa sekunneissa.

Vierailija
Ihan mielenkiinnosta kokeilin omaa algoritmia VB:llä ja tuon ekan luvun 94683107 tekijät löytyi alle 0,3 ms. Tosin kovin isoja lukuja ei voi käyttää (Long-tyyppi ja Mod-funktio rajoittaa). Ei tämä toosakaan mikään huippunopea ole. Luvulla 493984863 meni 0,53 ms.



Teitkö ohjelman niin että kun eka luku löytyy niin alkuperäinen luku jaetaan sillä löytyneellä jolloin saat toisen luvun
--> Testataan toista löydettyä lukua tiettyyn rajaan asti löytyykö lisää tekijöitä vai ei (koko väliä ei tarvitse testata..)
Nopeuttaa huomattavasti kun lukujen koko kasvaa.
Vai testasitko raa'alla silmukalla vaan ?

Tosin kovin isoja lukuja ei voi käyttää (Long-tyyppi ja Mod-funktio rajoittaa).
Testattava luku voidaan pilkkoa osiin...
Yllä kuvaamani toimenpide auttaa myös tähän ongelmaan.

Jos lisäksi tekee tuolla aikaisemmin kertomistani "muistisäännöistä" aliohjelman niin entistä helpommaksi menee.

Vierailija

Juuri tuolla periaatteella sen tein. Aluksi testaan luvulla kaksi tutkimalla onko Luku Mod 2 = 0. Jos on, jaan kahdella ja testaan uudelleen. Jos ei ole nolla , kasvatan jakajaa yhdellä. Lopetan kun jakajan neliö on suurempi kuin Luku. Lähinnä kiinnostaa kuinka nopea paremmalla algoritmilla toteutettu ohjelma on.

Edit: Lisäsin ohjelmaan isommille luvuille sopivan saman algoritmin, jossa käytän decimal-muuttujaa ja Int-funktiota. Tottakai homma silloin hidastuu muutenkin kuin pitkien lukujen johdosta. Esim. luvun 493984863728044433 jakaminen tekijöihin 5001653 * 98764321261 vei aikaa 7 sekuntia. Jollain muulla kuin VB:llä homma hoituu varmasti nopeammin.

Vierailija
korant
Juuri tuolla periaatteella sen tein. Aluksi testaan luvulla kaksi tutkimalla onko Luku Mod 2 = 0. Jos on, jaan kahdella ja testaan uudelleen. Jos ei ole nolla , kasvatan jakajaa yhdellä. Lopetan kun jakajan neliö on suurempi kuin Luku.

Jakajaa ei kannata kasvattaa joka kerta yhdellä. Jos luvusta on jo saatu kaikki kakkoset tekijäksi, niin ei enää parillisilla kannata yrittää jne. Nopeuttaisi jo huomattavasti, jos hyppää aina ei-jakavan luvun monikerroista yli, vähän samaan tyyliin kuin Eratostheneen seulalla etsitään äärellisestä joukosta alkulukuja.

Vierailija
kurnimaha
KBolt
Jos jostain kumman syystä joskus tarvitsee todella suuria lukuja käsitellä niin teen probleemasta ohjelmanpätkän jolla homma hoituu nopeasti. Helppoa mutta yksinkertaista. Yksinkertaisista operaatioista selviää jo taulukkolaskennalla jos tietää mitä tekee.

Nyt taidat yliarvioida ohjelmointitaitojasi ja/tai aliarvioida ongelman haastavuutta. Jos todella osaisit kehittää nopean tekijöihinjakoalgoritmin, niin saisit luultavasti Fieldsin mitalin ja samalla mullistaisit koko kryptografian.



Sekä tiedostojen pakkaamisen. Olen haaveillut aina "avainluvuista", alkuluvuista joiden muodostama eksponentti tai tulo tai mikä tahansa yhdistelmä muodostaisi lukuarvon, joka binäärinä vastaisi esim. jotain monen sadan megatavun ohjelmaa.

Piratismi säästäisi kaistaa huomattavasti jos voisi kertoa avainluvut tyyliin:

"Windows Vista Professional avainluvut: (62436246 potenssiin 2636 potenssiin 236247) + 9"

Tuon siis kun laskisi niin saisi siis tulokseksi täsmälleen saman binäärin. Se olisi tiedostonpakkausta parhaimmillaan.

Noiden avainlukujen selvittäminen ei vaan ole kovin helppoa. Pala kerrallaan, mutta sitten kasvaa lukujen määrä jo aika suureksi, ja sitä myöten pakkausteho laskee.

Sivujuonteena voi mainita sen mielenkiintoisen ajatuksen, että jossain mielessä ajatellen jokaista kirjoitettua ohjelmaa voi kuvata sen binäärin muodostamana numerona.

Numerona!? Se on minusta käsittämätöntä että eräs numero tarkoittaa vaikkapa räiskintäpeliä ja toinen bollywood-elokuvaa... Tarkoittaa siis sitä tietenkin ainoastaan silloin kun kontekstina on tietokone eli prosessori, mutta on se silti outoa...

Vierailija
kurnimaha

Jakajaa ei kannata kasvattaa joka kerta yhdellä. Jos luvusta on jo saatu kaikki kakkoset tekijäksi, niin ei enää parillisilla kannata yrittää jne. Nopeuttaisi jo huomattavasti, jos hyppää aina ei-jakavan luvun monikerroista yli, vähän samaan tyyliin kuin Eratostheneen seulalla etsitään äärellisestä joukosta alkulukuja.
Joo, hiffasin kyllä tuon ja loikin kolmosen jälkeen vain parittomien lukujen kautta eli kasvatan jakajaa kahdella. Se on helppo toteuttaa ja nopeus kasvaa lähes kaksinkertaiseksi mutta ei oleellisesti. Alkuluvut taas muodostaa niin julmetun taulukon ettei sellaista viitsi käyttää. Se seitsemän sekuntia putos alle neljän. VB on hidas isoilla luvuilla, saattaa mennä minuuttejakin joillain pitkillä luvuilla varsinkin jos sattuu olemaan alkuluku.

Sivut

Uusimmat

Suosituimmat