home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10503 < prev    next >
Encoding:
Text File  |  1992-08-21  |  2.1 KB  |  60 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!gatech!mailer.cc.fsu.edu!fsu1.cc.fsu.edu!rose
  3. From: rose@fsu1.cc.fsu.edu (Kermit Rose)
  4. Subject: Re: Primes
  5. Message-ID: <1992Aug22.040442.17832@mailer.cc.fsu.edu>
  6. News-Software: VAX/VMS VNEWS 1.3-4   
  7. Sender: news@mailer.cc.fsu.edu (Usenet News File Owner)
  8. Nntp-Posting-Host: fsu1.cc.fsu.edu
  9. Reply-To: rose@fsu1.cc.fsu.edu
  10. Organization: Florida State University
  11. References: <9208171021.aa01492@Paris.ics.uci.edu> <1992Aug18.091619.10152@waikato.ac.nz>
  12. Distribution:  world
  13. Date: 21 AUG 92 23:59:30    
  14. Lines: 44
  15.  
  16. In article <1992Aug18.091619.10152@waikato.ac.nz>, bill@waikato.ac.nz writes...
  17. >In article <9208171021.aa01492@Paris.ics.uci.edu>, kibler@turing.ICS.UCI.EDU (Dennis Kibler) writes:
  18. >> In mathematica the number of primes less than n or equal to n
  19. >> is given by PrimePi[n].
  20. >> 
  21. >> The following took about 1 second to compute.
  22. >> 
  23. >> 
  24. >> 
  25. >>  Do[Print[i," ",PrimePi[2^i]],{i,30}]
  26. >> 1 1
  27. >> 2 2
  28. >> 3 4
  29. >> 4 6
  30. >> 5 11
  31. >> ....
  32. >> 28 14630843
  33. >> 29 28192750
  34. >> 30 54400028
  35. >> 
  36. > 
  37. >Does anyone know how Mathematica stores its table of primes, and how efficient
  38. >it is in terms of space and access time? What's the minimum space a table
  39. >of primes can be compressed into if constant access time to find the nth prime
  40. >is required?
  41. > 
  42. >Bill Teahan,
  43. >Systems Programmer,
  44. >University of Waikato,
  45. >Hamilton, New Zealand.
  46. >"I have never been lost, but I will admit to being confused for several weeks."
  47. >-- Daniel Boone.
  48.  
  49. In general, one can use a bitmap to represent a prime number table.  Some 
  50. compression can be obtained by representing only odd numbers, or only 
  51. odd numbers not divisible by 3.  
  52. Then the computer can count primes by using the count bits function of the 
  53. hardware amazingly fast.  If the computer does not have a count bits 
  54. function, then this technique is lost.
  55.  
  56. rose@fsu1.cc.fsu.edu          To be sure I see your response, use e-mail.
  57. -----------------------------------------------------------------------
  58. You may post, repost, or publish ANY communication received from me.
  59. Be of good cheer, for it is much more fun than being depressed.
  60.