Posted By

Scooter on 05/23/09


Tagged

math


Versions (?)

Who likes this?

3 people have marked this snippet as a favorite

wizard04
nelda751
benrudolph


Prime Numbers


 / Published in: ASP
 

URL: http://reusablecode.blogspot.com/2009/05/prime-numbers.html

A library of functions related to prime numbers.

  1. <%
  2. ' ASP Mathematics Library - Prime Numbers
  3. '
  4. ' Copyright (c) 2009, reusablecode.blogspot.com; some rights reserved.
  5. '
  6. ' This work is licensed under the Creative Commons Attribution License. To view
  7. ' a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or
  8. ' send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California
  9. ' 94305, USA.
  10.  
  11. ' Finds prime numbers up to the limit.
  12. function getPrimes(limit)
  13. dim primality
  14. dim primeNumbers
  15.  
  16. primeNumbers = Array(2)
  17.  
  18. ' If the limit is less than 2, there is nothing to return since 1 and 0 are not prime.
  19. if limit < 2 then
  20. getPrimes = nothing
  21. exit function
  22. end if
  23.  
  24. ' Check all odd numbers, up to limit, against known primes only.
  25. for i = 3 to limit step 2
  26. primality = true
  27.  
  28. for each x in primeNumbers
  29. if i mod x = 0 then
  30. primality = false
  31. end if
  32. next
  33.  
  34. if primality = true then
  35. redim preserve primeNumbers(UBound(primeNumbers) + 1)
  36. primeNumbers(UBound(primeNumbers)) = i
  37. end if
  38. next
  39.  
  40. getPrimes = primeNumbers
  41. end function
  42.  
  43. ' Determine if a number is prime; modular division against odd numbers.
  44. function isPrime(candidate)
  45. isPrime = false
  46.  
  47. ' 0 and 1 are not prime, and neither is anything divisible by 2 or 3.
  48. if candidate < 2 or (candidate > 3 and (candidate mod 2 = 0 or candidate mod 3 = 0)) then
  49. exit function
  50. end if
  51.  
  52. if candidate > 5 then
  53. ' We only need to check up to the square root of the number.
  54. for i = 5 to Sqr(candidate) step 2
  55. if candidate mod i = 0 then
  56. exit function
  57. end if
  58. next
  59. end if
  60.  
  61. isPrime = true
  62. end function
  63.  
  64. ' Determine if a number is prime; modular division against known primes.
  65. ' Requires getPrimes(); for large numbers this might be faster than the guessing method above.
  66. ' NOTE: speed tests have shown that this method is actually slower!
  67. function isPrime2(candidate)
  68. dim primeNumbers
  69.  
  70. isPrime2 = false
  71.  
  72. ' 0 and 1 are not prime.
  73. if candidate < 2 then
  74. exit function
  75. end if
  76.  
  77. ' Make sure the array is not empty.
  78. if sqr(candidate) > 2 then
  79. primeNumbers = getPrimes(sqr(candidate))
  80. else
  81. primeNumbers = Array(2)
  82. end if
  83.  
  84. for each x in primeNumbers
  85. ' Dividing a number by itself shouldn't cause the test to fail.
  86. if candidate mod x = 0 and candidate <> x then
  87. exit function
  88. end if
  89. next
  90.  
  91. isPrime2 = true
  92. end function
  93.  
  94. ' Count the number of prime numbers less than or equal to x.
  95. function primeCount(x)
  96. primeCount = uBound(getPrimes(x)) + 1
  97. end function
  98.  
  99. ' Determines if a number is composite; opposite of prime.
  100. function isComposite(candidate)
  101. if isPrime(candidate) then
  102. isComposite = false
  103. else
  104. isComposite = true
  105. end if
  106. end function
  107.  
  108. ' Speed test between isPrime and isPrime2
  109. function isPrimeSpeedTest(value)
  110. response.write "test value is " & value & "<br>"
  111.  
  112. startTime1 = Timer
  113. result1 = isPrime(value)
  114. response.write "isPrime returned " & result1 & " in " & Timer - startTime1 & " seconds.<br>"
  115.  
  116. startTime2 = Timer
  117. result2 = isPrime2(value)
  118. response.write "isPrime2 returned " & result2 & " in " & Timer - startTime2 & " seconds.<br>"
  119. end function
  120.  
  121. call speedTest(179426491)
  122. %>

Report this snippet  

You need to login to post a comment.