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