Greg_Deckler's avatar
Greg_Deckler
Community Champion
7 years ago

IsPrime

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.

 

 

 

 

 

Mathematical

1 Reply

  • Anonymous's avatar
    Anonymous
    Not applicable
    5 years ago

    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.