[Challenge] Prime Number Printer

Here is my Python 3 submission for “Intermediate Difficulty”.

I leverage the use of primeNumberDetector() from my “Basic Difficulty” submission.
Just slightly modified in order to accept four digit numbers and I got rid of the product.
I use a “regular expression” and findall, to extract any numeric strings from the parameter,
and then generate all sub-strings of each numeric string and test each one for being prime.

Here is a link to my code:

https://repl.it/IdEb/2

Here is my revised Python 3, primeNumberDetector() submision:
It should handle integers up to 2147483647, Java Integer.MAX_VALUE

primes = [2]

def primeNumberDetector(l):
    if l < 2:
        return False
    if l in primes:
        return True
    for m in primes:
        if l%m == 0:
            return False
    return True

# 46337 is the largest prime whose square is less than 2147483647, Java Integer.MAX_VALUE
for n in range(3,46339,2):
    if primeNumberDetector(n):
        primes.append(n)

for n in range(2147483579,2147483649,2):
    if primeNumberDetector(n):
        print(n)

""" verified  that
        2147483579
        2147483587
        2147483629
        2147483647
    are all prime at:
    
https://www.calculatorsoup.com/calculators/math/prime-factors.php
"""

Here is a repl.it link:

https://repl.it/IdEb/4

Hard (semi hard at least)

https://repl.it/IfAK/0

Basic Difficulty, Python 3

from math import sqrt
# function to generate a prime number sieve
def gen_sieve(lim):
  # function to retrieve next prime index in sieve
  def nextPrime(n):
    n += 1
    while not s[n]:
        n += 1
        continue
    return n
  i = u = lim + 1
  j = k = 0
  s = [1] * i
  s[0] = 0
  s[1] = 0
  while k < sqrt(u):
    j = nextPrime(k)
    k = j
    while j + k < u:
      j += k
      s[j] = 0
  return s
# standalone prime detector
def primeNumberDetector(x):
  # for basic submission
  if x > 999: return "Range Error"
  try:
    s = gen_sieve(abs(int(x)))
    return not not s[x]
  except:
    raise ValueError
print (primeNumberDetector(99))
print (primeNumberDetector(997))

https://repl.it/IgAr/0

The sieve is first studied in JS in my earlier submission.

Note:

All memory used by the sieve is garbage collected immediately once the detector has returned a result.

1 Like

Intermediate in Ruby

https://repl.it/IgB2/0

There are two problems: to find all the numbers contained in a given string - and to check each one whether it is prime or not. So, we’ve to perform this check several times - OK, lets build a table of all primes (upto a given limit) and then simple lookup will answer whether any candidate substring is a prime or not. But how big should be the limit? Of course - the greatest value of the substrings
. The rest is trivial - we have to scan the string twice: once for finding the maximum value of the substrings, than build the table of primes, and second scan for performing the actual check. Thanks God, Ruby has a beautiful mechanism to write the procedure (extracting the numerical substrings) only once and then use it many times for many different actions. And the table - the Sieve of Eratosthenes is a good candidate (it is simple but efficient, especially if common optimisations are included - O(n log log n)); of course. there’re more efficient algorithms described (O(n) for the Sieve of Atkin), but lets stay with Eratosthenes for now.
Here is the code

def primeNumberPrinter(d)
  def subs(s)
    (0...s.size).each do |f|
      next unless s[f] =~ /[0-9]/
      (f...s.size).each do |t|
        break unless s[t] =~ /[0-9]/
        yield s[f..t].to_i
      end
    end
  end
  
  maxN = 3
  subs(d) {|n| maxN = n if n > maxN}
  sN = Math.sqrt(maxN).to_i
  noPrime = Array.new
  noPrime[0] = noPrime[1] = true
  3.step(sN, 2) do |p| # only odd numbers "sieved"
    next if noPrime[p]
    (p ** 2).step(maxN, 2 * p) {|i| noPrime[i] = true}
  end
  res = Array.new
  subs(d) {|n| res << n if n==2 || n.odd? && !noPrime[n]}
  return res
end
p primeNumberPrinter("abc2134kd31")

Basic level in Ruby

The code is at https://repl.it/IgBi/0
The first thought - the Sieve_of_Eratosthenes (of course, by no means - trial division by sequential numbers: anybody who read “The Art of Computer Programming” at least once in a life knows that). But - the goal is to check only ONE particular number, not to find all the primes less than any given limit: there’re more efficient algorithms known for primality test than sieve. Literature search reveals, that for numbers upto 64 digits the Baillie–PSW primality test is used in practice. But - it is (in my oppinion) too complicated for the current challenge; so let’s stay with the Eratosthenes. Unlike the intermediate level, the whole sieve is not necessary - we can break the process when we mark first time our target number as non-prime.
Here is the code

def primeNumberDetector(maxN)
  return true if maxN == 2  
  return false if maxN < 2 || maxN.even? 
  sN = Math.sqrt(maxN).to_i
  noPrime = Array.new
  3.step(sN, 2) do |p| # only odd numbers "sieved"
    next if noPrime[p] # already marked: with all multiples 
      (p ** 2).step(maxN, 2 * p) do |i| # skip even numbers
        return false if maxN == i
        noPrime[i] = true
      end
  end
  return true
end
p primeNumberDetector(13)
p primeNumberDetector(797)
p primeNumberDetector(799)

A post was split to a new topic: Prime Number Printer - thought experiment and test cases

Hard (in Ruby)

The code (for Basic level) is at https://repl.it/Ig0I/0
The code (for Intermediate level) is at https://repl.it/Ig0d/0
the solution that it is as efficiently as possible? So - don’t try to code your own primality test. Trust the provider of the system libraries - they’ve coded it the most optimal way, I’m sure. Well - I replace my own implementations of primality tests given above with calls to the home classes module “Prime” - and the code is below:

Basic level
def primeNumberDetector(maxN)
require ‘prime’
return Prime.prime? maxN
end
p primeNumberDetector(13)
p primeNumberDetector(797)
p primeNumberDetector(799)

Intermediate level

def primeNumberPrinter(d)
  require 'prime'
  def subs(s)
    (0...s.size).each do |f|
      next unless s[f] =~ /[0-9]/
      (f...s.size).each do |t|
        break unless s[t] =~ /[0-9]/
        yield s[f..t].to_i
      end
    end
  end
  
  res = Array.new
  subs(d) {|n| res << n if Prime.prime?(n)}
  return res
end
p primeNumberPrinter("abc2134kd31")

Intermediate level with Python

Uses a sieve to create sets of prime numbers in which numbers extracted from string are checked.
I have written 3 helper functions:

  • euler_sieve - constructs a set containing prime numbers below a specified limit (int representation of a digit string) using Euler’s Sieve
  • extract_numbers_text - takes a string and extracts the digit strings
  • extract_numbers_numstring - uses double loop to find all the numbers in a digit string, with lengths not exceeding a specified limit

The primeNumberPrinter extracts string digits from the input string. For each digit string, a sieve is created, containing all prime numbers smaller or equal to the int representation of a string digit. Then, a digit string is mined for numbers, which are aggregated in a list. The list is then compared with contents of the sieve and only numbers found in a sieve are reported in the output.

[EDIT] The code was corrected to test for all numbers, regardless of their length (previously testing only for numbers below 1000).

https://repl.it/IeCH/19

Documented as needed, otherwise the poetry is in the code…

``` from math import sqrt from itertools import combinations

function to generate a prime number sieve

def gen_sieve(lim):

function to retrieve next prime index in sieve

def nextPrime(n):
n += 1
while not s[n]:
n += 1
continue
return n
i = u = lim + 1
j = k = 0
s = [1] * i
s[0] = 0
s[1] = 0
while k < sqrt(u):
j = nextPrime(k)
k = j
while j + k < u:
j += k
s[j] = 0
return s

function to extract whole numbers in order

def number_extractor(test_str):
num_list =
ns = test_str
while len(ns):
if not ns[0].isdigit():
ns = ns[1:] if len(ns) else ns
else:
num = ‘’
while ns and ns[0].isdigit():
num += ns[0]
ns = ns[1:]
num_list.append(num)

return num_list

filter to detect primes

def filter_primes(nums):
s = gen_sieve(max(nums))
return list(filter(lambda x: not not s, nums))

function to filter number in test string

def filter_in_str(nums, test_str):
return list(filter(lambda x: str(x) in test_str, nums))

function to join tuples of number strings into an integer

def combine_nums(nums):
return [int(’’.join(x)) for x in nums]

#function to generate combinations of given r value
def generate_combs(nums, r):
return list(combinations(nums, r))

function to filter prime numbers in a string

def primeNumberPrinter(test_str=’’):
if not isinstance(test_str, str):
return “Input Error: Not string data”
nums = number_extractor(test_str)
if len(nums) < 1: return “Input Error: No numbers in test string”
pnp =
for i in range(len(nums)):
n = nums[i]
m =
for k in range(len(n)):
c = generate_combs(list(n), k + 1)
m += combine_nums©
pnp += filter_in_str(m, test_str)
return filter_primes(pnp)

test = primeNumberPrinter(‘abc123def45gh67ijk89lm’)
print (test) # [2, 3, 23, 5, 7, 67, 89]
test = primeNumberPrinter(‘abc2134kd31’)
print (test) # [2, 3, 13, 3, 31]
test = primeNumberPrinter(‘abc125789’)
print (test) # [2, 5, 7, 89, 257, 125789]
test = primeNumberPrinter(’_abc_123_def’)
print (test) # [2, 3, 23]
test = primeNumberPrinter(‘abcdefgh’)
print (test) # Input Error: No numbers in test string
test = primeNumberPrinter()
print (test) # Input Error: No numbers in test string
test = primeNumberPrinter(123)
print (test) # Input Error: Not string data

</details>

 https://repl.it/IiSQ/1
1 Like

My take on this week’s challenge.

Basic Difficulty:

https://repl.it/IhOI/3

Simple, concise recursion.

In the basic difficulty I simply check if the given number is less than one, if it is I return True meaning it is a Prime Number, I also check if it is divisible by itself meaning the number is a prime number as well.


Hard Difficulty:

https://repl.it/IhOG/4

This one really gave me trouble :persevere:, it kept returning <filter object at 0x7f36ffeb9eb8> when I tried to use a lambda for it so I then reverted to list comprehension which came through for me! :relieved:

For this one I used Three Lines of List Comprehension! but still maintained an efficient amount of Time Complexity. :smile:

filtered = [x for x in list(sent) if x.isdigit()]

The line above removes everything that’s not a number.

[nums.append(int(x)) for x in filtered]

This line above converts the list items which were strings to integers.

list(set(nums) - {x for x in range(max(nums)+7) for y in range(2,x) if x%y == 0 or x == y}))

This last line is where all the magic happens! So I turn the numbers into a set(), although the list() method isn’t necessary here it doesn’t hurt to take extra, extra precautions :sweat_smile: I then loop over the list once and then a second time this time checking if the number is a prime number.

1 Like

@dave.n research filter objects and iterators, they are very useful in the long run. If you really want to work with a list you can say list(filter(lambda...))

1 Like

Okay, here is my Python submission for “Hard Difficulty”:

primes = [2]

def primeNumberDetector(n):
    if n < 2:
        return False
    for m in primes:
        q,r = divmod(n,m)
        if q < m: # same test as (n < m*m)
            return True
        if r == 0: # m is a (prime) factor
            return False
    return True

# 46337 is the largest prime whose square is less than 2147483647, Java Integer.MAX_VALUE
for i in range(3,46339,2):
    if primeNumberDetector(i):
        primes.append(i)
        
import re

def primeNumberPrinter(t):
    print([int(s[i:i+j+1])
            for s in re.findall(r'\d+', t)
            for i in range(len(s))
            for j in range(len(s[i:]))
            if primeNumberDetector(int(s[i:i+j+1]))])
            
from random import choice, seed, randrange, getrandbits
from string import ascii_lowercase

def candidate():
     s = ''
     s += ''.join(choice(ascii_lowercase) for i in range(randrange(2,6)))
     s += str(getrandbits(randrange(3,32)))
     s += ''.join(choice(ascii_lowercase) for i in range(randrange(2,6)))
     s += str(getrandbits(randrange(3,32)))
     return s
     
def test_primeNumberPrinter(t):
    print("primeNumberPrinter(\"%s\")=" % t)
    primeNumberPrinter(t)

seed(123)
test_primeNumberPrinter("abc2134kd31")
test_primeNumberPrinter("abc2137kd31")
test_primeNumberPrinter(candidate() )
test_primeNumberPrinter(candidate() )
test_primeNumberPrinter(candidate() )
test_primeNumberPrinter(candidate() )
test_primeNumberPrinter(candidate() )
test_primeNumberPrinter(candidate() )

I have done some optimization of primeNumberDetector by deleting a useless operation:

    if n in primes:
        return True

and by adding an early termination test, essentially sqrt(n) < m:

        q,r = divmod(n,m)
        if q < m: # same test as (n < m*m)
            return True

Here is a link to my code in repl.it:

https://repl.it/Ig2g/36

Will most definitely look into it, especially after this challenge :triumph: :sweat_smile: It had my brain sifting through possible ways to solve this problem at 0(n) lol.


I’ll edit my solution once I turn these lines into one,

nums = []
filtered = [x for x in list(sent) if x.isdigit()]
[nums.append(int(x)) for x in filtered]

I believe it is possible yes?

2 Likes

Below is my answer to this challenge, basing on the principles of the primality test to know if a number is a prime.

The answer satisfy both Intermediate difficulty and hard difficulty.

All the comments are in the code

https://repl.it/Ib4E/9

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 105. 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 1010.

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 p2 < hh instead of pp < hi

Code running on repl.it here.

1 Like

Basic challenge

Thanks i found it at last

[](http://)

https://repl.it/InAg/1

This was yet another very interesting challenge.

Many people either implemented checking primes properly or implemented getting the numbers from the string in the first place properly. Few combined both, so well done to those who did.
Those that did both then either used hard coded arrays or sieves to check the primes. Since Dan specifically said the number could be infinitely long Trial division was the best solution here.

For managing to combine all these elements into one very well explained program @b-twin is the winner.

Again sorry for announcing the winner so late, and don’t forget to check out the new challenges!

4 Likes