## Posted By

Scooter on 05/23/09

## Who likes this?

3 people have marked this snippet as a favorite

# Prime Numbers

/ Published in: ASP   A library of functions related to prime numbers.

`<%    ' ASP Mathematics Library - Prime Numbers    '    ' Copyright (c) 2009, reusablecode.blogspot.com; some rights reserved.    '    ' This work is licensed under the Creative Commons Attribution License. To view    ' a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or    ' send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California    ' 94305, USA.     ' Finds prime numbers up to the limit.    function getPrimes(limit)        dim primality        dim primeNumbers         primeNumbers = Array(2)         ' If the limit is less than 2, there is nothing to return since 1 and 0 are not prime.        if limit < 2 then            getPrimes = nothing            exit function        end if         ' Check all odd numbers, up to limit, against known primes only.        for i = 3 to limit step 2            primality = true             for each x in primeNumbers                if i mod x = 0 then                    primality = false                end if            next             if primality = true then                redim preserve primeNumbers(UBound(primeNumbers) + 1)                primeNumbers(UBound(primeNumbers)) = i            end if        next         getPrimes = primeNumbers    end function     ' Determine if a number is prime; modular division against odd numbers.    function isPrime(candidate)        isPrime = false         ' 0 and 1 are not prime, and neither is anything divisible by 2 or 3.        if candidate < 2 or (candidate > 3 and (candidate mod 2 = 0 or candidate mod 3 = 0)) then            exit function        end if         if candidate > 5 then            ' We only need to check up to the square root of the number.            for i = 5 to Sqr(candidate) step 2                if candidate mod i = 0 then                    exit function                end if            next        end if         isPrime = true    end function     ' Determine if a number is prime; modular division against known primes.    ' Requires getPrimes(); for large numbers this might be faster than the guessing method above.    ' NOTE: speed tests have shown that this method is actually slower!    function isPrime2(candidate)        dim primeNumbers         isPrime2 = false         ' 0 and 1 are not prime.        if candidate < 2 then            exit function        end if         ' Make sure the array is not empty.        if sqr(candidate) > 2 then            primeNumbers = getPrimes(sqr(candidate))        else            primeNumbers = Array(2)        end if         for each x in primeNumbers            ' Dividing a number by itself shouldn't cause the test to fail.            if candidate mod x = 0 and candidate <> x then                exit function            end if        next         isPrime2 = true    end function     ' Count the number of prime numbers less than or equal to x.    function primeCount(x)        primeCount = uBound(getPrimes(x)) + 1    end function     ' Determines if a number is composite; opposite of prime.    function isComposite(candidate)        if isPrime(candidate) then            isComposite = false        else            isComposite = true        end if    end function     ' Speed test between isPrime and isPrime2    function isPrimeSpeedTest(value)        response.write "test value is " & value & "<br>"         startTime1 = Timer        result1 = isPrime(value)        response.write "isPrime returned " & result1 & " in " & Timer - startTime1 & " seconds.<br>"         startTime2 = Timer        result2 = isPrime2(value)        response.write "isPrime2 returned " & result2 & " in " & Timer - startTime2 & " seconds.<br>"    end function     call speedTest(179426491)%>`

You need to login to post a comment.