Srodne teme
06.12.2001. Prime numbers
22.11.2001. Cookies ?
23.03.2005. Volontiranjem do posla?
12.08.2005. Sugestije za prevod
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Prime Palindromes

[es] :: Art of Programming :: Prime Palindromes

[ Pregleda: 4212 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Humanoid
Hrvatska

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

ICQ: 170788654


Profil

icon Prime Palindromes10.10.2003. u 14:23 - pre 253 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


+605 Profil

icon Re: Prime Palindromes10.10.2003. u 18:46 - pre 253 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

icon Re: Prime Palindromes10.10.2003. u 19:49 - pre 253 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

icon Re: Prime Palindromes10.10.2003. u 21:09 - pre 253 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

icon Re: Prime Palindromes11.10.2003. u 07:14 - pre 253 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

icon Re: Prime Palindromes16.10.2003. u 21:26 - pre 252 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

icon Re: Prime Palindromes06.02.2004. u 16:31 - pre 249 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

icon Re: Prime Palindromes18.04.2004. u 13:40 - pre 246 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

icon Re: Prime Palindromes18.04.2004. u 20:30 - pre 246 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)..
 
Odgovor na temu

TRIŠESTPET
Split , Hrvatska

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

ICQ: 162376918


Profil

icon Re: Prime Palindromes26.04.2004. u 11:51 - pre 246 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: 8632
*.dial.InfoSky.Net



+2791 Profil

icon Re: Prime Palindromes02.05.2004. u 02:37 - pre 246 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: 8632
*.dial.InfoSky.Net



+2791 Profil

icon Re: Prime Palindromes02.05.2004. u 02:49 - pre 246 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

[es] :: Art of Programming :: Prime Palindromes

[ Pregleda: 4212 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
06.12.2001. Prime numbers
22.11.2001. Cookies ?
23.03.2005. Volontiranjem do posla?
12.08.2005. Sugestije za prevod
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.