Math 2325
Chapter 4 - Prime Numbers

The function PrimeQ will tell you  whether or not a number is prime. (Same as text's Prime Test program.)

PrimeQ[17]

PrimeQ[15]

The function ListPrimes will list the primes less than or equal to n for you.

ListPrimes[n_] := Prime[#] &  /@  
          Range[PrimePi[n]];

ListPrimes[100]

The function PrimePi will count the number of prime numbers less than n. (Same as text's Count Primes program.)

PrimePi[100]

You can use these functions to do more complicated computations.  Just as an example, the following command computes the proportion of primes in the first 1000 numbers.

N[PrimePi[1000]/1000]

Functions generating primes

You can use the below command (plugging a formula into the PrimeQ function) to do the text's Mersenne Check (or, similarly, any other formula you like).

PrimeQ[2^17 - 1]

The function EulerCheck will check the first n values of function p, and print the ones that are prime.  (Note that p must be defined with x as its variable.)

EulerCheck[p_, n_] := 
        Select[((p /. x -> #) &  /@  Range[n]), 
          PrimeQ];

EulerCheck[41 + x + x^2, 20]

Primes mod 4

The program PrimeOneThree will check the primes up to n, and report how many are 1 (mod 4) and how many are 3 (mod 4), as well as the total.  (Comparable to text's Count Primes Mod 4.)

PrimeOneThree[n_] := 
        Module[{primelist, ones,  total,  
            threes}, 
primelist = 
            Prime  /@  Range[PrimePi[n]]; 
ones = 
            Count[Mod[#, 4] &  /@  primelist,  
              1]; 
total = 
            Length[primelist]; 
threes = 
            total - ones - 
              1 ;   
Print["Total:     ", 
            total]; 
Print["1 (mod 4): ", 
            ones]; 
Print["3 (mod 4): ", 
            threes];
];

PrimeOneThree[100]

Art Duval, artduval@math.utep.edu
February 27, 2005
Revised March 4, 2005