Forum Discussion
Lambda for Prime Numbers in a Range
OK so I can't believe I didn't think of this sooner. I just reduced the time in 1/2 again by only looking at the odd numbers so now the sequence of numbers in the range of interest will only be the odd numbers but I did have to play with it a bit to include the number 2 in the end if needed so hopefully someone can improve on that. Here is the updated LAMBDA with a time mark of 1.5s for 1-100,000:
=LAMBDA(low, high,
LET(
rng, SEQUENCE(
(high - ISEVEN(high) - IF(low < 3, 1, low + ISEVEN(low)) + 2) / 2,
1,
IF(low < 3, 1, low + ISEVEN(low)),
2
),
rngo, SEQUENCE(1, MAX(INT(SQRT(high) / 2), 1), 3, 2),
list, BYROW(IF(rng > rngo, MOD(rng, rngo), 1), LAMBDA(in, AND(in))) *
IF(rng = 1, 2, rng),
FILTER(list, list, "none")
)
)all these improvements also improve the range it can be used on. the original would error out due to resources but the newer ones I could run on 1-200,000 with times: 11.5, 9.8, 4.3s respectively and then only this last version would run on 1-300,000 which took 7.7s and found 25,997 prime numbers can that even be right? Now I'm questioning if I'm running into calc errors in excel...
I had a run through for ideas. I got to BYROW/MOD/AND but found you were there ahead of me.
You halved the count of numbers to test by eliminating even numbers. A further reduction could be to remove multiples of 3 as well by generating numbers
= LAMBDA(low,high, LET( k, SEQUENCE(QUOTIENT(high-low,3),1,1+MROUND(low,6),3), k+ISEVEN(k) ) )Another thought is to perform the extraction in tranches. For example, to identify primes in the range 32-1000 you only need to test against the 10 primes in the range 2-31. That is not too exciting but, for the next tranche 1,000-1,000,000, you only need to test against the ~144 primes over 2-997 that you have already found.
As for timing, I use Charles Williams's functions that time calculations to μs.
I carried out the 3-step process and took 5sec to determine 78330 supposed primes between a thousand and a million. My active range wen to FR333002 which is probably a cell I have never seen before. It was probable a mistake to lay the test primes out as a row array. Both could have been columns if I were to use MAP rather than BYROW for the modulo calculation.
= FILTER( number#, MAP(number#, LAMBDA(n, AND(MOD(n,prime)))))Note: This did improve the used range,
- just a quick update. I incorporated your concept of counting by 3 instead of 2 but had to tweak it a bit (I will post the updated code later) and happy to say it cut the timing in half again. Now that is done, I hope to use it and try a recursive solution.
- this is fantastic. I will play with that counting by 3. I also like your thoughts on creating tiers and will try recursive calls finding primes in tiers but suspect I'll hit arrays of arrays issues but I'll see what I can work out. As for the timing, do you have a link for Charles Williams's resource? I did a search and found some interesting videos (killed a few hours lol) but could you give me a link to the functions your are referring to. Thank you
I went on to Charles's website because I thought the timing routines were available without charge. I have a macro-enabled workbook that contained them but I haven't used it recently because I have his Profiler add-in. I am therefore not sure whether the original version that I have is specific to 32 bit calculation or will work with 64 bit installations.
I have attached a copy of the primes workbook that I used for experimentation, though I reduced the integers in cell F3 (number) to limit the used range and memory requirements.
[Added: I will be interested to see how recursion (or even REDUCE with thunks) work out.]
