[VA] SRC #013 - Pi Day 2023 Special
|
03-19-2023, 04:31 AM
(This post was last modified: 03-19-2023 06:45 AM by 2old2randr.)
Post: #9
|
|||
|
|||
RE: [VA] SRC #013 - Pi Day 2023 Special
I could only find a recursive implementation for the inclusion/exclusion method but this turns out to be much slower than the earlier brute force solution (even given the list of primes a priori). Just for giggles, here are the run times for the first two numbers using this approach - I did not bother running for the others.
Number Count Approximation Runtime (Seconds) -------------------------------------------------------- 12,345 7,503 3.14198204634 140.36 100,000 60,794 3.14155932716 902.63 The code - in case someone wants to try converting it to an iterative solution which should be much faster. « → number « primes 2. ^ DUP SIZE 0 → squares nsquares count « « → prefix startpos add? « IF prefix number ≤ THEN startpos nsquares FOR i IF squares i GET number > THEN nsquares 1 + 'i' STO @ exit loop ELSE prefix squares i GET * DUP IF number > THEN DROP ELSE DUP number SWAP / IP IF add? THEN count + ELSE count SWAP - END 'count' STO i 1 + add? NOT combinations EVAL END END NEXT END » » → combinations « 1 1 1 combinations EVAL number count - DUP number 6 * SWAP / √ » » » » Sudhir |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)