CFLib.org – Common Function Library Project

GetPrimes(topInt)

Last updated July 31, 2004

Version: 3 | Requires: ColdFusion 5 | Library: MathLib

 
Rated 0 time(s). Average Rating: 0

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

Return Values:
Returns an array.

Example:

view plain print about
<cfdump var="#getprimes(1000)#">

Parameters:

Name Description Required
topInt The number to calculate primes for. Yes

Full UDF Source:

view plain print about
<cfscript>
/**
 * 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;
}
</cfscript>
blog comments powered by Disqus

Search CFLib.org


Latest Additions

Adam Cameron Adam Cameron added
createPrimeNumbe...
14 day(s) ago

Ray Ford Ray Ford added
timeZoneNow
29 day(s) ago

Henry Ho Henry Ho added
queryExecute
a while ago

Rick Root Rick Root added
deleteDirectory
a while ago

Top Rated

Darwan Leonardo Sitepu backupDatabase
Rated 5.0, 48 time(s)

Barney Boisvert indentXml
Rated 5.0, 12 time(s)

Rachel Lehman deAccent
Rated 5.0, 9 time(s)

Darwan Leonardo Sitepu splitNumber
Rated 5.0, 8 time(s)

Created by Raymond Camden / Design by Justin Johnson