[es] - Prime Palindromes

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

^{10.10.2003. u 14:23}

Naisao sam na zadatak u kojem u intervalu [5,100000000] za 5(!)sekundi moram naci sve proste palindrome(kao npr. 7,11,131,itd.) .Postoji li tako brz algoritam u kojem bih ja za 5s nasao takve brojeve(sve sto sam dosad probao bilo je presporo,ukljucujuci i Eratostenovo sito,provjera do korjena).Jednostavno sam ostao bez ideja.Ima li tko kakvu ideju kako to napraviti?

^{10.10.2003. u 14:23}

Bojan Basic
Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3821
*.mobtel.co.yu

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

Profil

Re: Prime Palindromes

^{10.10.2003. u 18:46}

Za pocetak, nema potrebe da proveravas brojeve sa parnim brojem cifara, jer su deljivi sa 11.

Ljubičice crvena, što si plava kô zelena trava.

^{10.10.2003. u 18:46}

stalker
Branko Kokanovic
Beograd

Član broj: 11897
Poruke: 601
*.drenik.net

Profil

Re: Prime Palindromes

^{10.10.2003. u 19:49}

Ako ti ista znaci,svi palindromi koji u sebi imaju 1,0 ili 2 kada se kvadriraju daju opet palindrom,pa mozes odmah da ih ozbacis kao slozene.
npr. 10201x10201=104060401

^{10.10.2003. u 19:49}

stalker
Branko Kokanovic
Beograd

Član broj: 11897
Poruke: 601
*.drenik.net

Profil

Re: Prime Palindromes

^{10.10.2003. u 21:09}

•Pored brojeva sa parnim brojem cifara mozes da izbacis i brojeve sa neparnim brojem cifara kojima je prva(tj. poslednja) cifra parna.(mozes tom logikom onda da izbacis i one koje poccinju sa 5).Tako si od 100...000 brojeva dosao do cetvrtine tog broja.
•Takodje (sad najbolja optimizacija!) kad krenes od 100 ides do prvog polindroma (101) i posle brojis za 10(111,121,131...).Uopsteno,za n-cifreni broj(n=2k+1) krenes od 10...01 (n-1 nula) i ispitujes "prostocu" skakanjem za 100..000 (k-1 nula).Npr. 10001,10101,10201.
•OBRATI PAZNJU!!! da kada se menja prva cifra ne skace se za toliko (29992,30003) nego,VALJDA (nisam zagledao) za 11.(ali to ti i ne treba ako primenis prvu optimizaciju)
•Jos ti ostaje da nadjes neki "fini" algoritam za ispitivanje da li je broj prost (googlaj) i eto te na cilju za manje od 5 min

(cak i ako radis u VB-u;brrrr) Jos ako programiras u asm-u,ima da ga izvuces za manje od minut

Srecno trazenje

^{10.10.2003. u 21:09}

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

Re: Prime Palindromes

^{11.10.2003. u 07:14}

Ne,radim u Free Pascalu.
Hvala na savjetima.

^{11.10.2003. u 07:14}

Bijeli_dedA
Jurica Cerovec
Zagreb

Član broj: 10238
Poruke: 9
*.cmu.carnet.hr

Profil

Re: Prime Palindromes

^{16.10.2003. u 21:26}

Ovako. Vjeroatno ti je jasno da je palidroma manje nego prostih brojeva. Prema tome možeš generirati palindrome pa za njih provjeravati da li su prosti. Znači, ideš od 1 do 10000, dopišeš mu sve osim zadnje znamenke obrnuti redoslijedom i provjeriš da li je prost (još ga možeš ubrzati ovim gore optimizacijama). Znam jer sam rješavao taj zadatak prije dosta vremena i radilo je savršeno.

^{16.10.2003. u 21:26}

shumi
Ivan Karadži�?
Novi Sad

Član broj: 20363
Poruke: 1
*.adsl.net.hinet.hr

ICQ: 1242355
Sajt: www.google.com

Profil

Re: Prime Palindromes

^{06.02.2004. u 16:31}

Za informaciju: svi prim-brojevi hoće da zadovoljavaju uvet 2^(n-1) mod n = 1

^{06.02.2004. u 16:31}

TRIŠESTPET
Split , Hrvatska

Član broj: 24877
Poruke: 4
*.cmu.carnet.hr

ICQ: 162376918

Profil

Re: Prime Palindromes

^{18.04.2004. u 13:40}

Ako koga to još zanima,evo najbrži (IMHO) algoritam za provjeravanje da li je broj prost.Najbitnija stvar je korištenje Bitwise operatora (^).Mislim da je ostalo jasno.

Code:

int prime(long broj)
{
   if (broj==1 || broj%2==0) return 0;
   if (broj==3 || broj==5) return 1; else if (broj%3==0) return 0;
   int i=5;
   int k=4;
   do {
      if (broj%i==0) return 0;
      k^=6;
      i+=k;
   } while (i*i<=broj);
   return 1;
}

^{18.04.2004. u 13:40}

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
195.252.85.*

Sajt: localhost

Profil

Re: Prime Palindromes

^{18.04.2004. u 20:30}

ne znam da li je to najbrži algoritam (mislim da nije), ali znam da pod jedan nije tačan (kada je broj=2, greši), i pod dva, da korišćenje bitwise operatora ne da nije najbitnija, nego je najmanje bitna stvar u tom algoritmu.

umesto njega, mogla je da stoji mnogo čitljivija linija k=(k==4?2:4). a ako neko želi da prigovori kako je ovo sporije nego originalna linija (bar za jedan ciklus), odgovaram da o brzini očigledno nije vođeno računa, čim se pri svakom prolazu kroz petlju nepotrebno izračunava kvadrat i*i (mogao je koren broja da se izračuna jedared, pa da se upoređuje).

(možda ima još nekih potencijalnih ubrzanja, ali nisam stručan)..

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

^{18.04.2004. u 20:30}

TRIŠESTPET
Split , Hrvatska

Član broj: 24877
Poruke: 4
*.cmu.carnet.hr

ICQ: 162376918

Profil

Re: Prime Palindromes

^{26.04.2004. u 11:51}

Ona dvica je lapsus...
Nisam bio siguran da li je najbrzi- zato stoji ono IMHO
Za ovaj zadatak je dovoljno brz (pod uvjetom da se prvo prave palindromi pa onda provjera da li su prosti) , jer za brojeve u intervalu od 1 - 100 000 000 izbacuje rjesenja u 0,01...

^{26.04.2004. u 11:51}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
*.dial.InfoSky.Net

Profil

Re: Prime Palindromes

^{02.05.2004. u 02:37}

Što se tiče najbržeg poznatog testa primalnosti, pogledati sledeću temu.

http://www.elitesecurity.org/tema/52064

To jedino ima smisla koristiti kod brojeva sa velikim brojem cifara.

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{02.05.2004. u 02:37}

Nedeljko
Nedeljko Stefanović
Beograd

Član broj: 314
Poruke: 5628
*.dial.InfoSky.Net

Profil

Re: Prime Palindromes

^{02.05.2004. u 02:49}

Dakle, trebaju ti naviše sedmocifreni prosti palindromi. Pa to su osim 2,3,5,7 i 11 još jedino prosti brojevi koji se dobijaju od četvorocifrenih i dvocifrenih nadovezivanjem njihovih "slika u ogledalu". Treba generisati sve takve palindrome, četvorocifrenih i dvocifrenih brojeva nema mnogo, pri čemu vodeća cifra tog dvocifrenog, odnosno četvorocifrenog broja ne može biti parna niti petica. Eratostenovo sito možeš da koristiš na početku za određivanje prostih brojeva do 999 sa kojima ćeš ispitivati deljivost tvojih brojeva. To bi trebalo da ti završi posao za manje od 5 sekundi.

Pishi kao shto govorish, a chitaj kao shto je napisano.

^{02.05.2004. u 02:49}