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

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

•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

Ne,radim u Free Pascalu.
Hvala na savjetima.

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.

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

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.

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

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

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

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.