Da li je broj u nizu prost? :))

[ Nikolavlasotince @ 03.05.2008. 20:04 ] @

Mozda je naziv teme glup al nisam znao kako da je nazovem :) Ali to nije bitno.
Treba da napravim function u pascalu koja ce mi za uneti broj vracati boolean true ako je broj prost ili false ako je broj slozen. E sad naravno, lako je napraviti takvu funkciju za broj. Ali problem je sto je meni ta funckija potrebna za broj sa 1000, 2000, ... i 10000 cifara. Ja taj broj cuvam u neki niz. Svaku cifru posebno. Npr. broj 10937 cuvam ovako: niz[1] = 1 niz[2] = 0 niz[3] = 9 niz[4] = 3 niz[5] = 7 znaci [1, 0, 9, 3, 7]. E sad kako odrediti da li je taj broj koji cuvam u nizu prost?

Pozz

[ savkic @ 03.05.2008. 21:12 ] @

Pogledaj http://en.wikipedia.org/wiki/Primality_test i http://en.wikipedia.org/wiki/Prime_number.

[ Nikolavlasotince @ 03.05.2008. 21:46 ] @

Ma procitao sam. Ali to je teorija prostih brojeva. Znam ja da dodjem do prostog broja ako treba da ispitam dal je broj tipa LongINt integer ili slicno prost. Samo problem je sto je meni broj niz. Objasnio sam gore kako cuvam taj broj. Ali posto moram da proveravam i za broj koji ima 10 000 cifara, znaci da moram da delim i sa brojem koji ima prilicno velik broj cifara i moram i delilac da cuvam u niz. A onda ne znam kako da napravim funkciju koja daje ostatak pri deljenju niza nizom. Npr. [1, 4, 5, 6, 2] kada delim brojem [1, 4, 1] koliki ostatak dobijam?

[ savkic @ 04.05.2008. 00:10 ] @

Pitanje o računskim operacijama nad velikim brojevima koji se čuvaju kao stringovi je bilo pre nekoliko meseci, pogledaj tu diskusiju.

[ Nikolavlasotince @ 04.05.2008. 00:43 ] @

Pronasao sam samo ovo: http://www.elitesecurity.org/t297314-0 Aritmetika nad velikim brojevima. Da li je to to? Tu sam pronasao funkciju za mod ali je problem sto je moj delilac prevelik da bi stao u smallInt. Ja i delilac cuvam u niz. "onda bi morao da se izdeli na manje delove, svaki se od njih podeli i na kraju se zbroje rezultati" video sam i ovo ali ne znam kako to da izvedem :(

[ savkic @ 04.05.2008. 11:30 ] @

Verovatno će ti biti najlakše da iskoristiš već postojeće biblioteke za rad sa velikim brojevima, verovatno su sve u C/C++, mada je moguće da postoje i neke za Pascal. Pogledaj NTL, http://www.shoup.net/ntl. Dat je i primer testa prostih brojeva, http://www.shoup.net/ntl/doc/tour-ex1.html.

[ bytefx192 @ 04.05.2008. 11:46 ] @

Ok, hvala puno. Snaci cu se na dalje sam.

[ Nikolavlasotince @ 04.05.2008. 14:11 ] @

<Ok, hvala puno. Snaci cu se na dalje sam.>

^^ Greskom sam odgovorio sa acc-a mog brata :S