Welcome to BitCell. Click here to register !
- pentru i de la 7 la 1
- //vectorul cifre retine cifrele de la i la 1, inclusiv
- cifre = i,i-1,...1
- executa
- //functia concatenare intoarce numarul format prin concatenarea cifrelor din vectorul primit ca parametru
- numar = concatenare(cifre)
- daca eprim(numar)
- afiseaza(numar)
- opreste executia programului
- sfarsit daca
- //functia permutareaprecedenta intoarce cea mai mare permutare, mai mica decat cea primita ca parametru (din punct de vedere lexicografic)
- cifre = permutareaprecedenta(cifre)
- cat timp cifre!=1,2,...i
- precedentul i
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?
Cea mai simpla si mai proasta metoda prin care se poate rezolva aceasta problema este sa cautam primul numar mai mic decat 10^9 care respecta proprietatea de a fi pandigital si este, de asemenea, prim. Un astfel de program este extrem de ineficient.
Pentru o rezolvare inteligenta, vom observa ca numerele pandigitale de 9 si respectiv 8 cifre nu pot fi prime! Pentru a demonstra asta, tot ce trebuie sa facem este sa calculam suma cifrelor. Numerele pandigitale de 8 cifre vor avea suma cifrelor 36 (8*9/2), iar cele de 9 cifre, vor avea suma cifrelor 45. Astfel, acestea nu pot fi prime, pentru ca sunt divizibile oricum cu 9 (sau 3).
Acum, numarul cazurilor de la rezolvarea initiala se vor micsora cu foarte mult.
Totusi ... n-ar fi mult mai eficient daca ati putea genera direct numerele pandigitale ? O astfel de rezolvare, bazata pe permutari ale cifrelor, s-ar scrie astfel:
Eu v-am prezentat metoda care am folosit-o, va astept si pe voi
!
