Python: How to get Prime Numbers from string using Permutations and Combinations-CodePudding

Complete the following function to return a list of strings lesser than 999 which form prime numbers from a given string of numbers. For example if the given string is “23167”. All the prime numbers less than or equal to 999 in the string are 2,3,23,31,7,167. So, your function must return [2,3,23,31,7,167]. Although 23167 is a prime number we can ignore it because it is greater than 999. Output: should be list of integers

def primenumber_from_string(string1):
    #your code goes here
    return []

if _name=='main_':
    #you can run any test cases here
    print(primenumber_from_string("8487934"))

CodePudding user response：

Approach the problem systematically. Start with all the possible one-digit numbers, and check if they are prime. Then try all the possible two-digit numbers and see if they are prime. Then try all the possible three-digit numbers and check them all. Lastly show your accumulated results in the expected format.

CodePudding user response：

So it's a basic algorithmic problem.
I'll give you some pseudo - code.
At this point, I'll only give you Brut-force solution, but I'll think about "proper" approach.
So:
Take first digit -> check
Second -> check
Third -> check
{ ... }
compose two digit numbers -> check.
When this is completed, put them into your list.
For checking if number is prime fast ( O(sqrt(N)) ) you can use this function:

## Made by kam021m on: 12.12.2019  ##
## Resources used:
## * GeeksForGeeks article how to check primes fast
## *
def is_prime(n):
    if n == 1:
        return False
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i  = 1
    return True

This basically checks if number is prime by % (i) when i is lower than sqrt from n.

If I'll find faster solution, I will post it here.
Greetings
kam021m
EDIT 1: also wanted to ask, is it your homework or sth? Do you have time limits on it?