IsPrime

Greg_Deckler — Sun, 10 Feb 2019 05:41:07 GMT

This nifty little Quick Measure will tell you if a number is prime or not.

mIsPrime = 
VAR __num = MAX([Number])
VAR __max = INT(SQRT(__num))
VAR __table = GENERATESERIES(2,__max,1)
VAR __table1 = ADDCOLUMNS(__table,"__mod",MOD(__num,[Value]))
RETURN
SWITCH(TRUE(),
    __num = 1, 0,
    ISBLANK(COUNTROWS(FILTER(__table1,[__mod]=0))),1,
    0
)

Basically, compute the nearest integer to the square root of the number. Generate a table of all values between 2 and that number. Compute the modulus of the number in question and each of the table values. If one of the rows has a modulus of 0, it's not a prime number.

Included in the file is a representation of the Ulam Spiral, a nifty little construct that occurs when you write positive integers down in a square spiral pattern like:

Apparently, Ulam discovered the spiral in 1963 while doodling during the presentation of "a long and very boring paper" at a scientific meeting. This narrows down the potential presentations by exactly 0.

eyJrIjoiZTg1YjIxMTktMjNhNi00MjVmLWFhM2YtYmI1MjA5Mjk0NThkIiwidCI6IjRhMDQyNzQzLTM3M2EtNDNkMi04MjdiLTAwM2Y0YzdiYTFlNSIsImMiOjN9

Re: IsPrime

Anonymous — Wed, 30 Jun 2021 08:40:44 GMT

This code has the potential to be much faster than the original. Its length stems from the fact that it has a lot of comments that should make it more understandable but if they're removed, it should be not much longer than the original (depens on formatting as well, of course).

mIsPrime = var __num = selectedvalue( [Number] ) var __numIsEvenAndNot2 = mod( __num, 2 ) = 0 && __num <> 2 var __isPrime = switch( true(), __numIsEvenAndNot2 || __num = 1, // Checking the condition above // speeds up the whole original code // since here we don't have to // create the series and then filter // the table if the number is even // (<>2) or 1. 0, __num = 2, 1, // At this point we know the number // is odd and greater than 2. var __max = int( sqrt( __num ) ) var __tableOfRemainders = addcolumns( union( row( "@PotentialDivisor", 2 ), // We only need to generate the odd // potential divisors, so this // again cuts the amount of // calculations by a factor of 2. generateseries(3, __max, 2) ), "@IsZeroRemainder", mod( __num, [@PotentialDivisor] ) = 0 ) var __hasNoRemainderOfZero = // Again, isempty most likely speeds // up the code compared to the original // since this function has the potential // to return before it scans the whole table // (which is needed for the countrows // function). isempty( filter( __tableOfRemainders, [@IsZeroRemainder] ) ) return // If __hasNoRemainderOfZero is true, // the number must be prime. int( __hasNoRemainderOfZero ) ) return __isPrime

Actually, I was interested in the speed differences... and here they are:

I ran a benchmark in DAX Studio. Here's the query:

// DAX Query DEFINE VAR __DS0FilterTable = TREATAS( { "My Formula" // or "Your Formula" }, 'Algorithms'[Algorithm] ) VAR __DS0FilterTable2 = TREATAS( { ( "[900,001; 1,000,000]" ) }, 'Numbers'[HundredThousands] ) EVALUATE SUMMARIZECOLUMNS( __DS0FilterTable, __DS0FilterTable2, "v__Primes", IGNORE( 'Numbers'[# Primes] ) )

Not gonna enlarge upon the results. The conclusion is that the new formula above is 40%-43% faster than the original one. The measure [# Primes] takes a set of currently visible numbers--in this case it was a set of integers { 900,001;....;1,000,000 }, so 100,000 in total---and calculates the number of primes among them using the two competing formulas. It does a simple iteration through the set and counts the number of 1's returned by the formula under scrutiny.

topic IsPrime in Quick Measures Gallery

IsPrime

Re: IsPrime