%Implementation of "Smartest Sieve" from Sieve Timing :)
%Assumes symbol /primes is defined
/isPrime {
/x exch def
/ip true def
/i 0 def
/for2 {
/p primes i get def
x p mod 0 eq {
/ip false def
} {
p p mul x le {
/i i 1 add def
for2
} if
} ifelse
} def
for2
ip
} def
/primeSieve {
/N exch def
/primes N array def
primes 0 2 put
primes 1 3 put
primes 2 5 put
/primeLength 3 def
/n 7 def
/for1 {
n isPrime {
primes primeLength n put
/primeLength primeLength 1 add def
} if
/n 2 n mul 3 mod 2 mul n add def
n N lt {
for1
} if
} def
for1
} def
%Assumes symbol /primes is defined
/partialSum {
/sum 0 def
/high exch def
/low exch def
/k low def
/for3 {
/sum sum primes k get add def
/k k 1 add def
k high lt {
for3
} if
} def
for3
sum
} def
/BOUND 1000000 def
%Method defines symbols /primes and /primeLength
%We do not use any return value
BOUND primeSieve
/ans 0 def
/maxChainLength 1 def
/lindex 0 def
/for4 {
lindex primeLength lt {
/hindex lindex maxChainLength add def
hindex primeLength lt {
/psum lindex hindex partialSum def
/for5 {
hindex primeLength lt psum BOUND lt and {
psum isPrime {
/ans psum ans max def
/maxChainLength hindex lindex sub def
} if
/psum psum primes hindex get add def
/hindex hindex 1 add def
for5
} if
} def
for5
/lindex lindex 1 add def
for4
} if
} if
} def
for4
ans pstack pop
Thursday, July 10, 2014
Problem 50 - Postscript
I have been working out a solution to the next problem, problem 88, and I figured I wanted a pretty capable language for my solution to that one, so I decided to free up such a language. Now, the language i had free to do this freeing up with was Postscript. Prior to this project, my main experiences with Postscript had been writing an interpreter for a subset of the language, and using the language way back when in my initial 24 hour run to solve problem 7. Now, however, I used Postscript to free up C, which means that I used it to solve problem 50. Once I got into the swing of things, the stack-basedness wasn't too bad, the main issues that arose were due to my inability to parse error messages, causing bugs to be hard to remove (and, as would be expected when using an unfamiliar programming paradigm, bugs abounded). This problem gave me a chance to write an implementation of my smarter sieve method from my analysis before...though in my attempt to also generate an independent isPrime method, I messed up at first (an independent isPrime method cannot assume the input number is not divisible by 2 or 3, it actually needs to check that!). But anyway, other than lots of little mistakes like that, things weren't too bad. Postscript isn't the most blazingly fast language though, so even with a number of optimizations that were not present in my C solution to problem 50, the solution below runs in about 50 seconds on my machine, whereas my C solution ran in about 0.5s. But either way, it runs in under a minute, so it is acceptable. Now, to solve problem 88 in C.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment