Find largest left truncatable prime in a given base: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Add Fortran.) |
|||
| Line 296: | Line 296: | ||
The initial idea is to see how far 32-bit integers will suffice, to try out the logic for the search. The basic idea is to maintain a "horde" of digit sequences that represent a prime number, then for each survivor in the horde, try adding a possible digit at the high-order end and checking that the resulting number is a prime. If so, add this sequence to the horde. When all trials have been made, if there was an addition, purge the earlier entries, and have another go, which is the next level up. If no addition had been made, then the sequence is ended, and the largest value amongst the survivors is printed. |
The initial idea is to see how far 32-bit integers will suffice, to try out the logic for the search. The basic idea is to maintain a "horde" of digit sequences that represent a prime number, then for each survivor in the horde, try adding a possible digit at the high-order end and checking that the resulting number is a prime. If so, add this sequence to the horde. When all trials have been made, if there was an addition, purge the earlier entries, and have another go, which is the next level up. If no addition had been made, then the sequence is ended, and the largest value amongst the survivors is printed. |
||
Fortran does not offer a "list" data structure, so as ever, fiddling with arrays is needed. The situation at the end of a level is that there are entries 1:LH, the "starters" for that level, and following that are entries LH + 1:NH, the added entries. The "starters" are no longer needed and to save on storage, this hole is to be filled. The entire horde could be shifted down LH slots, but there could be many of them. Instead, the tail end entries are copied from the end into the hole. There are of |
Fortran does not offer a "list" data structure, so as ever, fiddling with arrays is needed. The situation at the end of a level is that there are entries 1:LH, the "starters" for that level, and following that are entries LH + 1:NH, the added entries. The "starters" are no longer needed and to save on storage, this hole is to be filled. The entire horde could be shifted down LH slots, but there could be many of them. Instead, the tail end entries are copied from the end into the hole. There are of course many variations possible, such as using linked-lists with an "available entry" list so that only links need be messed with rather than copying content, etc. |
||
The source file uses the F90 style, mainly because module PRIMEBAG (from [[Extensible_prime_generator#Fortran]]) is available to supply some prime numbers and check whether a number is prime or not. This works up to the 32-bit integer limit: although INTEGER*8 variables are available, that seemed a reasonable stopping point. Otherwise, the source is older-style, except for a few conveniences: the use of "CYCLE" rather than a "GO TO", and an array assignment, rather than an explicit DO-loop. |
The source file uses the F90 style, mainly because module PRIMEBAG (from [[Extensible_prime_generator#Fortran]]) is available to supply some prime numbers and check whether a number is prime or not. This works up to the 32-bit integer limit: although INTEGER*8 variables are available, that seemed a reasonable stopping point. Otherwise, the source is older-style, except for a few conveniences: the use of "CYCLE" rather than a "GO TO", and an array assignment, rather than an explicit DO-loop. |
||
| Line 400: | Line 400: | ||
13 8 4 Integer overflow! 815730721 -1993454625 |
13 8 4 Integer overflow! 815730721 -1993454625 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||