Answered by:
Can I improve Prime Numbers calcurating by M ?

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
PrimeNumbers
Regards
Yoshihiro Kawabata
Question
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) Marked as answer by Yoshihiro Kawabata Saturday, October 26, 2013 12:54 AM
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) Marked as answer by Yoshihiro Kawabata Saturday, October 26, 2013 12:54 AM

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
 Edited by Yoshihiro Kawabata Saturday, October 26, 2013 1:47 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 :)
 From the Power Query ribbon, select Online Search.
 Search for "list of primes"
 The first result is "The first 500 prime numbers". Add that to your worksheet. DONE!

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 Edited by Yoshihiro Kawabata Saturday, October 26, 2013 3:45 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.

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 Eratosthenslet
// 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