Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 4 Notes > Section 4 > Page 909 > Note (a) Previous note-----Next note
Notes for: Systems Based on Numbers | The Sequence of Primes

*Finding primes

The sieve of Eratosthenes shown in the picture is an appropriate procedure if one wants to find every prime, but testing whether an individual number is prime can be done much more efficiently, as in PrimeQ[n] in Mathematica, for example by using Fermat's so-called little theorem that Mod[a^p-1, p] == 1 whenever p is prime. The n^th prime Prime[n] can also be computed fairly efficiently using ideas from analytic number theory (see below).


Page image


Pages related to this note:


All notes on this page:

* History of primes
* Finding primes
* Decimation systems
* Divisors
* Results about primes
* History of number theory
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note