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

Regards
Yoshihiro Kawabata

Friday, October 25, 2013 1:17 AM

• 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

### 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
• 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
• 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,

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