none
Can I improve Prime Numbers calcurating by M ?

    Question

  • Can I improve Prime Numbers calcurating by M ?

    I want to learn M language more and more.
    I try to calcurate Prime from 1 to 100.

    Result prime number worksheet:
    prime number table in Excel worksheet

    Prime number by M:

    let
         isPrime = (x as number, optional n as number) =>
         [
             n = if n = null then 2 else n,
             p = Number.RoundDown(x),
             r = if p < 2
                 then true
                 else
                     if Number.Mod(p, n) = 0
                     then false
                     else
                         if n > p / 2
                         then true
                         else @isPrime(p, n + 1)
         ][r],
         a = {1..100},
         TableFromList = Table.FromList(a, Splitter.SplitByNothing(), null, null, ExtraValues.Error),
         RenamedColumns = Table.RenameColumns(TableFromList,{{"Column1", "number"}}),
         InsertedCustom = Table.AddColumn(RenamedColumns, "Custom", each isPrime([number])),
         RenamedColumns1 = Table.RenameColumns(InsertedCustom,{{"Custom", "isPrime"}}),
         PrimeNumbers = Table.SelectRows(RenamedColumns1, each ([isPrime] = true))
    in
         PrimeNumbers

    Prime numbers by M

    Regards
    Yoshihiro Kawabata

    Friday, October 25, 2013 1:17 AM

Answers

  • Here's an approach based on the Sieve of Eratosthenes:

    let
        List.Sequence = (min, max) => List.Generate(() => min, (x) => x <= max, (x) => x + 1),
        FilterComposites = (candidates, value) => List.Select(candidates, (c) => Number.Mod(c, value) <> 0),
        List.Primes = (candidates) => let
            first = List.First(candidates),
            rest = List.Skip(candidates, 1),
            primes = if first = null then {} else {first} & GetPrimes2(FilterComposites(rest, first))
        in primes,
        GetPrimes2 = List.Primes,
        Table.Primes = (max) => Table.FromColumns({List.Primes(List.Sequence(2, max))}, {"Number"})
    in
        Table.Primes(100)

    Friday, October 25, 2013 2:04 PM
    Owner

All replies

  • Here's an approach based on the Sieve of Eratosthenes:

    let
        List.Sequence = (min, max) => List.Generate(() => min, (x) => x <= max, (x) => x + 1),
        FilterComposites = (candidates, value) => List.Select(candidates, (c) => Number.Mod(c, value) <> 0),
        List.Primes = (candidates) => let
            first = List.First(candidates),
            rest = List.Skip(candidates, 1),
            primes = if first = null then {} else {first} & GetPrimes2(FilterComposites(rest, first))
        in primes,
        GetPrimes2 = List.Primes,
        Table.Primes = (max) => Table.FromColumns({List.Primes(List.Sequence(2, max))}, {"Number"})
    in
        Table.Primes(100)

    Friday, October 25, 2013 2:04 PM
    Owner
  • Thank you, Curt

    NICE .. Sieve of Eratosthenes
    I am happy to meet M.

    I try small CHANGE : call @List.Primes instead of GetPrime2

    let
        List.Sequence = (min, max) => List.Generate(() => min, (x) => x <= max, (x) => x + 1),
        FilterComposites = (candidates, value) => List.Select(candidates, (c) => Number.Mod(c, value) <> 0),
        List.Primes = (candidates) => let
            first = List.First(candidates),
            rest = List.Skip(candidates, 1),
            primes = if first = null then {} else {first} & @List.Primes(FilterComposites(rest, first))
        in primes,
         Table.Primes = (max) => Table.FromColumns({List.Primes(List.Sequence(2, max))}, {"Number"})
    in
        Table.Primes(100)

    Regards,
    Yoshihiro Kawabata

    Saturday, October 26, 2013 12:56 AM
  • Great answer Curt. Some of us were sitting around this afternoon talking about how to do it (before we read your answer.) This was the fastest/easiest way we came up with... haha :)

    1. From the Power Query ribbon, select Online Search.
    2. Search for "list of primes"
    3. The first result is "The first 500 prime numbers". Add that to your worksheet. DONE!
    Saturday, October 26, 2013 3:21 AM
    Moderator
  • Yes, Ben

    Online Search - The first 500 prime numbers , unpivot.

    I start Excel Power Query at Online Search, From Facebook.
    and Unpivot, Filter, etc.
    Now, I want to learn M language,

    Online Serach  The first 500 prime numbers

    BI must be FAN
    Yoshihiro Kawabata


    Saturday, October 26, 2013 3:33 AM
  • Interestingly, one small change in code can make a significant difference in the execution profile. If we say

    FilterComposites = (candidates, value) => List.Buffer(List.Select(candidates, (c) => Number.Mod(c, value) <> 0)),

    that is, call List.Buffer on the result of List.Select, then the execution time on my machine for Table.Primes(1000) drops from 1.5 seconds to 23 ms. That's quite a difference!

    The reason for this is that M is both functional and lazy, so unless we buffer the output of List.Select, we're really just building a query that needs to be evaluated over and over. This is similar to the Enumerable functions in LINQ, if you're familiar with those.

    Saturday, October 26, 2013 6:51 PM
    Owner
  • Awesome, Curt.

    I like LINQ, and I like M, and I love performance by M.

    Prime Number by M with comments.

    // build prime number's table
    // based on Sieve of Eratosthens

    let
        // List.Sequence return number List  from min to max.
        List.Sequence = (min, max) => List.Generate(() => min, (x) => x <= max, (x) => x + 1),

        // FilterComposites return number List which cannot Mod by value in candidates's number List.
        // List.Buffer build List.Buffer without lazy.
        FilterComposites = (candidates, value) => List.Buffer(List.Select(candidates, (c) => Number.Mod(c, value) <> 0)),

        // List.Primes return prime number List from candidates number List.
        List.Primes = (candidates) => let
            // first return first number from candidates number List
            first = List.First(candidates),
            // rest return second or lator number List from candidates number List
            rest = List.Skip(candidates, 1),
            // primes return prime number List.
            primes =
                // compare between first and null
                if first = null
                    // if first is null then return empty List
                    then {}
                    // if first is not null then return number List with first and prime numbers in rest.
                    // FilterComposties calcurate number List which cannot Mod by first in rest.
                    // @ to call List.Primes itself
                    // List.Primes calcurate prime number List from FilterComposite result.
                    else {first} & @List.Primes(FilterComposites(rest, first))
            // return primes for List.Primes
            in primes,
             // Table.Primes return prime number Table from 2 to max
            Table.Primes = (max) => Table.FromColumns({List.Primes(List.Sequence(2, max))}, {"Number"})
     in
         // return prime number Table to 100
        Table.Primes(100)

    Regards,
    Yoshihro Kawabata

    Sunday, October 27, 2013 2:16 AM