A different variant of my previous submission for **hard** challenge, this time using a sieve to precalculate a number of primes. As no constrains were given regarding amount of numbers to appear in the string, their size (int is unlimited in Python) or strings length, I’ve set the max of precalculated primes (*prec*) to 10**5. This computes in fraction of a second at a relatively small memory cost and should speed up processing strings featuring large amouns of numbers up to 10**10.

Main code is largely the same as previously, but I changed the prime-checker to take advantage of the precalculated primes: primes under the *prec* level are already in the array passed to the function; bigger numbers will first be divided by primes in the array (composites up to *prec***2 must have a divider there), and further with the regular trial division. Considering that input string will contain relatively few very large primes, this seems the best option.

The sieve is my implementation of Erastothenes algorithm running at O(n/2) memory. Being an upgrade from a basic O(n) version it features an ugly bit in the form of exception handling where the formula to cross the composites sometimes goes off by 1. Big love to anyone who can help me find a correct formula - due to Python being interpreted rather than compiled, the crossing done with list slicing is vastly faster than using a while loop.

```
def sieve(hi): # memory O(hi/2)
if hi%2: hi += 1
hh = hi//2
nums = [1] * hh # nums matches [1,3,5,7,9,11,13,15,17,19,...,hh]
nums[0] = 0 # 1 is not prime
p = 3 # each actual number p = 2*px + 1
px = 1 # each index of p: px = (p-1)//2
while p*p < hi:
try:
nums[px:hh:p] = [0] * ((hh-1)//p + 1) # sorry
except ValueError:
nums[px:hh:p] = [0] * ((hh-1)//p)
nums[px] = 1
i = 1
while px+i < hh:
if nums[px+i]:
px += i
p = 2*px + 1
break
i += 1
return [2]+[2*loc+1 for loc,x in enumerate(nums) if x]
def isprime(n, sieved, precalcprimes):
if n == 2: return True
if n in [0,1] or (n % 2) == 0: return False
if n < sieved:
return n in precalcprimes
maxprime = int(n**(0.5))+1
for i in precalcprimes:
if (n % i) == 0 or i > maxprime: return False
for i in range(sieved+1, maxprime, 2):
if (n % i) == 0: return False
return True
def combs(text):
comblist = []
text = str(text)
tl = len(text)
for i in range(tl):
j = 1
while i + j <= tl:
comblist.append(int(text[i:i+j]))
j += 1
return tuple(comblist)
def isnumber(x):
return x in "0123456789"
def primeNumberPrinter(text):
prec = 10**5 # precalculated prime limit. Must be an even value!
lowprimes = sieve(prec)
text = "-" + text + "-" # start and end string with nondigits to
nums = [] # keep boundaries logic below simple
nx = 0 # nx holds index of begin of each digit series
for i in range(len(text)):
if isnumber(text[i]) and not nx: # nondigit/digit boundary
nx = i
elif not isnumber(text[i]) and nx: # digit/nondigit boundary
nums.append(text[nx:i])
nx = 0
return [x for i in nums for x in combs(i) if isprime(x, prec, lowprimes)]
```

**Edit**: Fixed nasty bug in sieve, was p*2 < hh instead of p*p < hi

Code running on repl.it here.