From: HJSmith@ix.netcom.com (Harry J. Smith) Newsgroups: alt.math.recreational,alt.sci.math.combinatorics,aus.mathematics,sci.math,sci.math.num-analysis Subject: Re: Algorithm for Primes Date: Sun, 14 Jun 1998 16:40:24 GMT "Reine Larsson" wrote: >Can someone tell me of a good algorithm for testing primes? I want to use >it in a program that counts how many primes that can be represented by a >positive 32-bit integer (max 2,147,483,647). > >I have by myself come up with the following: >If a test value A is not evenly divisibly with 2 then it is neither with >A/2. The same is valid for 3 – A/3, 4 – A/4, and so on. This means that you >continually can shorten the range of values that you have to check if A is >evenly divisibly with. > >Unfortunately this algorithm is a little bit to slow when I want to count >all primes that can be represented by the 32-bit integer, so I wonder if >there exists a better one that I can use. > > Reine This is what I got when I changed my program to work in powers of 2: PrimePi2 - Computes the Prime Pi(x) counting function Version 1.20, last revised: 1998-06-13, 1600 hours Copyright (c) 1981-1998 by author: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070. All rights reserved. Type any key to continue... (or Esc to quit) 3 = last prime < 2^2, #2. Elapsed time: 0.00 seconds. 7 = last prime < 2^3, #4. Elapsed time: 0.00 seconds. 13 = last prime < 2^4, #6. Elapsed time: 0.00 seconds. 31 = last prime < 2^5, #11. Elapsed time: 0.00 seconds. 61 = last prime < 2^6, #18. Elapsed time: 0.00 seconds. 127 = last prime < 2^7, #31. Elapsed time: 0.00 seconds. 251 = last prime < 2^8, #54. Elapsed time: 0.00 seconds. 509 = last prime < 2^9, #97. Elapsed time: 0.00 seconds. 1021 = last prime < 2^10, #172. Elapsed time: 0.00 seconds. 2039 = last prime < 2^11, #309. Elapsed time: 0.00 seconds. 4093 = last prime < 2^12, #564. Elapsed time: 0.00 seconds. 8191 = last prime < 2^13, #1028. Elapsed time: 0.00 seconds. 16381 = last prime < 2^14, #1900. Elapsed time: 0.00 seconds. 32749 = last prime < 2^15, #3512. Elapsed time: 0.00 seconds. 65521 = last prime < 2^16, #6542. Elapsed time: 0.05 seconds. 131071 = last prime < 2^17, #12251. Elapsed time: 0.05 seconds. 262139 = last prime < 2^18, #23000. Elapsed time: 0.16 seconds. 524287 = last prime < 2^19, #43390. Elapsed time: 0.38 seconds. 1048573 = last prime < 2^20, #82025. Elapsed time: 0.71 seconds. 2097143 = last prime < 2^21, #155611. Elapsed time: 1.54 seconds. 4194301 = last prime < 2^22, #295947. Elapsed time: 12.52 seconds. 8388593 = last prime < 2^23, #564163. Elapsed time: 20.54 seconds. 16777213 = last prime < 2^24, #1077871. Elapsed time: 41.69 seconds. 33554393 = last prime < 2^25, #2063689. Elapsed time: 69.53 seconds. 67108859 = last prime < 2^26, #3957809. Elapsed time: 101.12 seconds. 134217689 = last prime < 2^27, #7603553. Elapsed time: 168.07 seconds. 268435399 = last prime < 2^28, #14630843. Elapsed time: 311.81 seconds. 536870909 = last prime < 2^29, #28192750. Elapsed time: 591.27 seconds. 1073741789 = last prime < 2^30, #54400028. Elapsed time: 1175.40 seconds. 2147483647 = last prime < 2^31, #105097565. Elapsed time: 2468.57 seconds. 4294967291 = last prime < 2^32, #203280221. Elapsed time: 5643.98 seconds. pi(6741513313) = 312392500. Elapsed time: 10125.02 seconds. -Harry -- | Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070-4522, USA | Home Phone: 1 408 741-0406, Work Phone: 1 408 235-5088 (Voice Mail) | E-mail: HJSmith@ix.netcom.com, Fax: 1 408 235-2019 | Web site: http://www.netcom.com/~hjsmith --