06-08-2022, 04:50 PM
(06-08-2022, 02:49 PM)bplus Wrote: @JRACE
This was a nice catch on Danilin's code:
If j >= p ^ 0.5 Then f = 2 'original line moved outside inner loop
But as far as speed goes, sieving is way faster than testing so many times for divisibility with MOD. But you need an array to save results. Maybe the RC challenge was looking to do it without arrays? BUT who really needs to know the 10001th dang prime number? or any nth prime number. Most applications use primes info for factoring so you need to collect prime info in an array for vast range of factors and sieving is fastest for that to do something more practical than this RC challenge.
Sieving with wheels is even faster! The example I showed was sieving with a wheel of 6 the samllest, which takes out all multiples of 2 and 3 for prime candidates even before you start sieving. That's 1/2 of all numbers plus 1/3 of 1/2 = 1/6 of the remaining prime candidates.
Sieving with a 210 wheel; takes out 2, 3, 5, 7 multiples (2*3*5*7 = 210) before sieving with remaining prime candidates another speed improvement. The wheel size eventually get unwieldy but it depends on the number of integers your prime info (what I call array or first factors) needs to cover.
Re the catch: I started programming in the days of 8-bit, 64K max CPUs, when RAM was at a premium and even integer multiplies and divides were expensive, cycle-wise, so my eye is trained to spot little inefficiencies.
The RCode (I hesitate to use the initials RC on this site) page has no rules yet. It's not even a challenge at this point:
Quote:10001th prime is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
10001th prime
Task
Find and show on this page the 10001st prime number.
The sieve I posted leaves out multiples of 2 by design, but I've never (yet) experimented with wheels. I had thought about preemptively marking off the lower primes, but wasn't sure about the benefit and never even bothered. You introduced me to the term "wheels" in this usage.
The prog I posted was one of MANY translations I made of an example program from the Digital Mars website. After checking out DMDScript's speed (it may do well against older JavaScript engines, but it can't hold a candle to SpiderMonkey or V8), I went on a speed testing binge of several different compilers & interpreters. Granted, a sieve is not a well-rounded benchmark, but it was an amusing diversion (especially during slow times at work) until I got bored with it.
I've been programming mainly in C for many years and am weary of doing all the little things that one must do, over and over again, to craft a robust C program. I wanted a simpler way of creating small utilities and such on the fly. Anyway, my experiments led me to learn and use GAWK for a while, but I eventually came back home to Basic.