Chapter 04 - Primes.sagews

Chapter 4 - Primes

Algorithm 4.3 (Sieve of Eratosthenes)

The function defined below implements Algorithm 4.3. Note that Sage identifies the first element in a list as being in position 0. Thus, we have set our initial list of numbers to be sieved to start at 0 so that number k is in the k-th position of the list. We `cross out' an element of S by setting it equal to 0. The list P is obtained by picking off the positions in S (other than 1) that contain a nonzero entry

def sieve(n):
    S=[0..n]
    P=[]
    d=floor(sqrt(n))
    for i in [2..d]:
        if S[i]!=0:
            j=2*i;
            while j <= n:
                S[j]=0
                j=j+i
        i=i+1
    for i in [2..n]:
        if S[i]!=0:
            P.append(i)    
    return(P)

sieve(100)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Prime Factorization

The command factor(n) produces the prime factorization of n.

factor(100)            

2^2 * 5^2

The Prime Number Theorem

Table 4.1

table([(10^n,prime_pi(10^n),N(10^n/log(10^n)),N(prime_pi(10^n)/(10^n/log(10^n)))) for n in [1..6]], header_row=["x", "pi(x)","x/log(x)","pi(x)/(x/log(x))"], frame=True)

+---------+-------+------------------+-------------------+ | x | pi(x) | x/log(x) | pi(x)/(x/log(x)) | +=========+=======+==================+===================+ | 10 | 4 | 4.34294481903252 | 0.921034037197618 | +---------+-------+------------------+-------------------+ | 100 | 25 | 21.7147240951626 | 1.15129254649702 | +---------+-------+------------------+-------------------+ | 1000 | 168 | 144.764827301084 | 1.16050288686900 | +---------+-------+------------------+-------------------+ | 10000 | 1229 | 1085.73620475813 | 1.13195083171587 | +---------+-------+------------------+-------------------+ | 100000 | 9592 | 8685.88963806504 | 1.10431981059994 | +---------+-------+------------------+-------------------+ | 1000000 | 78498 | 72382.4136505420 | 1.08448994777908 | +---------+-------+------------------+-------------------+