[es] - Prime Palindromes

Humanoid
Hrvatska

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

ICQ: 170788654

Profil

^{10.10.2003. u 14:23 - pre 262 meseci}

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?

Odgovor na temu

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+621 Profil

Re: Prime Palindromes

^{10.10.2003. u 18:46 - pre 262 meseci}

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.

Odgovor na temu

stalker
Branko Kokanovic
Beograd

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

+2 Profil

Re: Prime Palindromes

^{10.10.2003. u 19:49 - pre 262 meseci}

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

Odgovor na temu

stalker
Branko Kokanovic
Beograd

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

+2 Profil

Re: Prime Palindromes

^{10.10.2003. u 21:09 - pre 262 meseci}

•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

Odgovor na temu

Humanoid
Hrvatska

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

ICQ: 170788654

Profil

Re: Prime Palindromes

^{11.10.2003. u 07:14 - pre 262 meseci}

Ne,radim u Free Pascalu.
Hvala na savjetima.

Odgovor na temu

Bijeli_dedA
Jurica Cerovec
Zagreb

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

Profil

Re: Prime Palindromes

^{16.10.2003. u 21:26 - pre 261 meseci}

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.

Odgovor na temu

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 - pre 258 meseci}

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

Odgovor na temu

TRIŠESTPET
Split , Hrvatska

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

ICQ: 162376918

Profil

Re: Prime Palindromes

^{18.04.2004. u 13:40 - pre 255 meseci}

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;
}

Odgovor na temu

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

Član broj: 4128
Poruke: 3448
195.252.85.*

Sajt: localhost

+5 Profil

Re: Prime Palindromes

^{18.04.2004. u 20:30 - pre 255 meseci}

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}}

Odgovor na temu

TRIŠESTPET
Split , Hrvatska

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

ICQ: 162376918

Profil

Re: Prime Palindromes

^{26.04.2004. u 11:51 - pre 255 meseci}

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...

Odgovor na temu

Nedeljko
Nedeljko Stefanović

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

+2801 Profil

Re: Prime Palindromes

^{02.05.2004. u 02:37 - pre 255 meseci}

Š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.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

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

+2801 Profil

Re: Prime Palindromes

^{02.05.2004. u 02:49 - pre 255 meseci}

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.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu