CFLib.org – Common Function Library Project

Description:
Creates an array of all the prime numbers from 1 to the specified integer.

Return Values:
Returns an array.

Example:

<cfdump var="#getprimes(1000)#">

Parameters:

Full UDF Source:

/**
 * Creates an array of all the prime numbers from 1 to the specified integer.
 * 
 * @param topInt      The number to calculate primes for. (Required)
 * @return Returns an array. 
 * @author Steven Van Gemert (svg2@placs.net) 
 * @version 3, July 31, 2004 
 */
function GetPrimes(topInt) {
    var stepInt = 0;
    var i = 0;
    var primes = arraynew(1);
    var di = 4; //Wheel factor.
    var maxfactor = 0;
    var thisnumberoffactors = 0;
    var thismaxfactor = 0;
    var isprime = "yes";

    if(topInt is 1) return primes;
    primes[1] = 2;
    if(topInt is 2) return primes;
    primes[2] = 3;
    if(topInt LTE 4) return primes;

    maxfactor = ceiling(sqr(topInt));
    primes = getPrimes(maxfactor); //Recursion call. Find the primes for the square root of the passed number.

    //Make the current maxfactor odd. We will use this as a starting point for checking for primes above the square root of this number.
    maxfactor = maxfactor + 1 + (1 * (not ((maxfactor + 1) mod 2)));

    //Now determine the appropriate wheel factor beginning value.
    if(not (maxfactor mod 3)){
        maxfactor = maxfactor + 2;
        di = 4;
    } else if(not ((maxfactor + 2) mod 3)){
        di = 2;
    }
    else{
        di = 4;
    }

    thisnumberoffactors = arraylen(primes);  
    for(stepInt=maxfactor; stepInt lte topInt; stepInt=stepInt+di) {
        di = 6 - di; //Implement wheel factor. Every third odd number will be divisible by 3. Don't check it.
    
        //This will be the limit to where we check for factors. There must be at least one factor less than the square root of the number.
        thismaxfactor = sqr(stepInt);

        isprime = "yes"; //Assume this number is prime.

        for(i=1; i LTE thisnumberoffactors; i = i + 1){ //For each factor...
            if(not (stepInt mod primes[i])){
            isprime = "no"; //Indicate that this number is not prime.
            break; //Break if we find a valid factor.
            } else if(primes[i] GT thismaxfactor){ //If we have reached the square root.
            break; //Stop processing...we have now validated this number as a prime.
            }
        }
        if(isprime)ArrayAppend(primes,stepInt); //If this number is prime, then add it to the array of primes.
    }

    return primes;
}