Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition

Section 4.5.4

1.  If d_k isn’t prime, its prime factors are cast out before d_k is tried.

2.  No; the algorithm would fail if p_t−1 = p_t, giving “1” as a spurious prime factor.

3.  Let P be the product of the first 168 primes. [Note: Although P = 19590 . . . 5910 is a 416-digit number, such a gcd can be computed in much less time than it would take to do 168 divisions, if we just want to test whether or not n is prime.]

4.  In the notation of exercise 3.1–11,

Σμ,λ2⌈lg max(μ+1,λ)⌉P(μ,λ)=1mΣl≥1f(l)Πk=1l−1(1−km),

where f(l) = ∑_1≤λ≤l^{2⌈ lg max(l+1–λ,λ)⌉}. If l = 2^k+θ, where 0 < θ ≤ 1, we have

f(l)=l2(3⋅2−θ−2⋅2−2θ),

where the function 3 · 2^−θ – 2 · 2^−2θ reaches a maximum of 98 at θ = lg(4/3) and has a minimum of 1 at θ = 0 and 1. Therefore the average ...