The running time of PrimalityTest

(* The formulas for the running time derived in class *)

size = 31;
N[Floor[√((2^size)-1)]-1]

N[Ceiling[(2^(size/2))]-2]

(* Below is a computation of the running time in years of PrimalityTest program posted on the class website on 1 terraFLOPS supercomputer, assumming the body of the loop consists of 1 floatin-point instruction. *)

size=150;
n=N[Ceiling[(2^(size/2))]-2] (* formula we derived *);
N[(n/(60(*secs*)×60(*mins*)×24(*hrs*)×365(*days*)))×(10^(-15))(* 1 petaFLOPS*)]

DiscretePlot[{Floor[(Sqrt[(2^m)-1])],Ceiling[(2^(m/2))]-2}, {m, 2, 150}]

(* Below are auxiliary checks *)

Limit[((Ceiling[(2^(m/2))]-2)/(2^(m/2))), m -> ∞]

Limit[((Floor[(Sqrt[(2^m)-1])]-1)/(2^(m/2))), m -> ∞]

DiscretePlot[Floor[(Sqrt[(2^m)-1])]-1-(Ceiling[(2^(m/2))]-2), {m, 2, 439}]