Forum Discussion

mtarler's avatar
mtarler
Silver Contributor
Feb 24, 2022

Lambda for Prime Numbers in a Range

So I need to get prime numbers to calculate Modulo 1021 for check characters on a UDI.  So I decided to create some Lambda functions.  I found some old Excel formula/code on the internet that I fixed some errors in and converted to some of the new available functions:

 

=LAMBDA(low, high,
    LET(
        rng, SEQUENCE(high - low + 1, 1, low),
        rngo, SEQUENCE(1, INT(SQRT(high)), 2),
        list, IF(
            MMULT(
                --(IF(rng > rngo, MOD(rng, (rng > rngo) * rngo)) = 0),
                TRANSPOSE(rngo)
            ) = 0,
            rng
        ),
        FILTER(list, list, "")
    )
)

 

this was already an improvement over the original code because a) it fixed a problem with the original using too small a range that it could identify non-prime numbers as prime and now only checks numbers up to SQRT(high) .  But easy improvement was to check only odd numbers but also had to check the number 2 (i.e. a prime must be an odd number except for 2) so:

 

=LAMBDA(low, high,
    LET(
        rng, SEQUENCE(high - MAX(2, low) + 1, 1, MAX(2, low)),
        rngo, SEQUENCE(1, MAX(INT(SQRT(high) / 2), 1), 3, 2),
        list, (MMULT(
            --(IF(rng > rngo, MOD(rng, rngo)) = 0),
            TRANSPOSE(rngo)
        ) = 0) * (ISODD(rng) + (rng = 2)) * rng,
        FILTER(list, list, "")
    )
)

 

ok that worked and then I tried another improvement to replace MMULT with BYROWS(...LAMBDA()):

 

=LAMBDA(low, high,
    LET(
        rng, SEQUENCE(high - MAX(2, low) + 1, 1, MAX(2, low)),
        rngo, SEQUENCE(1, MAX(INT(SQRT(high) / 2), 1), 3, 2),
        list, BYROW(IF(rng > rngo, MOD(rng, rngo), 1), LAMBDA(in, AND(in))) *
            (ISODD(rng) + (rng = 2)) * rng,
        FILTER(list, list, "none")
    )
)

 

So I did some speed checks on this and please tell me if there is a better way but I used the following formula:

 

=CHOOSE({1,2,3},NOW(),PrimesRange(1,100000),NOW())

 

and then in another cell I did a difference between the 2 NOW() cells

So the 1st Lambda took an average of about 10s

the 2nd Lambda was 3.8s

the last Lambda variation was 2.9s

 

This has a been a great teaching experience for me (including learning why I want to be careful using the IFS() statement and probably will go back to using nested IF() more often, thank you Joe User ) but I am also hoping to learn more and know if some colleagues here (e.g.  @Sergei Baklan  ,  @Riny_van_Eekelen  ,  @Peter Bartholomew @Hans Vogelaar ,  @NikolinoDE , and many others) can help me further improve the efficiency.  or even learn a better way to time test my functions.

thank you

 

 

5 Replies

  • mtarler's avatar
    mtarler
    Silver Contributor

    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...

     

     

    • PeterBartholomew1's avatar
      PeterBartholomew1
      Silver Contributor

      mtarler 

      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,

      • mtarler's avatar
        mtarler
        Silver Contributor
        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.

Resources