Skip to content
Advertisement

Split number into the primes inside it

So I have a list of numbers that look like “3723311723” and “13617172343”. As you can see these numbers can be split into prime numbers e.g “3723311723” could be split into 37, 23, 31 ect. How could I write a python program that takes a number like this as an input and returns a list of the primes inside it (in the order they are found)?

Thanks.

Advertisement

Answer

If you know that the numbers are definitely gonna be prime, then you just have to break up the string into substrings of length 2, right?

s = "37233141712331719337"
print([int(s[i:i+2]) for i in range(0, len(s), 2)])

Output:

[37, 23, 31, 41, 71, 23, 31, 71, 93, 37]

EDIT:

This does a recursive search to find non-overlapping primes. If there’s no valid split, it returns False. The usual caveats of recursion apply: if the input is too long, you’ll recurse too deep and the program will blow up. But you can use a stack instead of recursing if that’s an issue.

def is_prime(n):
    for k in range(2, n):
            if n % k == 0:
                    return False
    return True
def primesplit(s, i=0):
    if i+1 >= len(s):
        return []
    if i+2 <= len(s):
        two_digits = int(s[i:i+2])
        if is_prime(two_digits):
            remaining_digits = primesplit(s, i+2)
            if isinstance(remaining_digits, list):
                return [two_digits] + remaining_digits
    one_digit = int(s[i:i+1])
    if not is_prime(one_digit):
        return False
    remaining_digits = primesplit(s, i+1)
    if isinstance(remaining_digits, list):
        return [one_digit] + remaining_digits
    return False
s = "37233141712331719337"
result = primesplit(s)
print(result)
print("".join(map(str, result)) == s)

Output:

[37, 23, 31, 41, 71, 23, 31, 7, 19, 3, 37]
True
User contributions licensed under: CC BY-SA
4 People found this is helpful
Advertisement