#Written by Dennis Hou, Rutgers University, for the Experimental Math
#class of Jan. 28, 2010 

HelpDH:=proc(): print(`PrimeList_clever(n)`): 
print(` PrimeList_Sieve2_3_5:(n) `):
end:

IF_helper:=proc(n, k) local i, m:
i:=0:
m:=n:
while m mod k = 0 do
   m:=m/k:
   i:=i+1:
od:
i:
end:

IF:=proc(n) local i, L1, L2:
L1:=SA(n/2):
L2:=[]:
for i from 1 to nops(L1) do
   if IF_helper(n, L1[i]) > 0 then
      L2:=[op(L2), [L1[i], IF_helper(n, L1[i])]]:
   fi:
od:
L2:
end:

PFT_ratio:=proc(n) local i:
[seq(evalf(nops(SA(i))/(i/log(i))), i=1..n)]:
end:

# two changes to the original sieve function:
#
# minor: replace "i=2..n/j" with "i=j..n/j"
# (redundant calculations)
#
# major: replace "trunc(sqrt(n))" with "trunc(evalf(sqrt(n)))"
# trunc() takes much longer to process thousands of symbolic square roots than
# floating-point approximations
SE:=proc(n) local i,j:
{seq(i,i=2..n)} minus 
{seq(seq(j*i,i=j..n/j),j=2..trunc(evalf(sqrt(n))))}:
end:

# Theorem 8.8.4 in Bach-Shallit (1996): p(n) < n*log(n)+n*log(log(n))
PrimeList_clever:=proc(n):
convert(SE(evalf(n*log(n)+n*log(log(n)))), list)[1..n]:
end:

# functions that pre-sieve {2}, {2, 3}, and {2, 3, 5} respectively
PrimeList_Sieve2:=proc(n) local i, k, l, L:
L:=[2, 3]:
i:=2:
k:=3:
while i < n do
   k:=k+2:
   L:=[op(L), k]:
   for l in L[2..nops(L)-1] do
      if k mod l = 0 then
         i:=i-1:
         L:=L[1..nops(L)-1]:
         break:
      fi:
   od:
   i:=i+1:
od:
L:
end:

PrimeList_Sieve2_3:=proc(n) local i, j, k, l, L:
L:=[2, 3]:
i:=2:
k:=3:
j:=0:
while i < n do
   j:=j+1:
   k:=k+2:
   if j = 3 then
      j:=0:
   else
      L:=[op(L), k]:
      for l in L[3..nops(L)-1] do
         if k mod l = 0 then
            i:=i-1:
            L:=L[1..nops(L)-1]:
            break:
         fi:
      od:
      i:=i+1:
   fi:
od:
L:
end:

PrimeList_Sieve2_3_5:=proc(n) local a, b, i, k, l, L:
L:=[2, 3, 5]:
i:=3:
k:=5:
a:=1:
b:=0:
while i < n do
   a:=a+1:
   b:=b+1:
   k:=k+2:
   if a = 3 and b = 5 then
      a:=0:
      b:=0:
   elif a = 3 then
      a:=0:
   elif b = 5 then
      b:=0:
   else
      L:=[op(L), k]:
      for l in L[4..nops(L)-1] do
         if k mod l = 0 then
            i:=i-1:
            L:=L[1..nops(L)-1]:
            break:
         fi:
      od:
      i:=i+1:
   fi:
od:
L:
end:

PrimeList_SieveAll:=proc(n) local i, j, k, l, L1, L2:
L1:=[2, 3]:
L2:=[1]:
k:=3:
l:=0:
while nops(L1) < n do
   k:=k+2:
   for j from 1 to nops(L2) do
      if L2[j] = L1[j+1] then
         L2[j]:=1:
         l:=1:
      else
         L2[j]:=L2[j]+1:
      fi:
   od:
   if l = 1 then
      l:=0:
   else
      L1:=[op(L1), k]:
      L2:=[op(L2), 1]:
   fi:
od:
L1:
end: