-1

I've been playing with Python, and wrote the following code that finds all prime numbers in a given range as following:

def get_primes(x):
    primes = []

    def is_prime(x):
        if x == 0:
            return
        else:
            for i in range(2, int(x)):
                if (x % i) == 0:
                    return is_prime(x - 1)
            else:
                return x, is_prime(x - 1)

    primes.append(is_prime(x))
    return primes


print(get_primes(int(input("Enter the range: 0 - "))))

And the output is: (enter 100 for example)

Enter the range: 0 - 100
[(97, (89, (83, (79, (73, (71, (67, (61, (59, (53, (47, (43, (41, (37, (31, (29, (23, (19, (17, (13, (11, (7, (5, (3, (2, (1, None))))))))))))))))))))))))))]

that looks so ugly. So, I need a way to flatten the recursive tuple structure:

[97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2, 1]

i used the following code to do so:

x = get_primes(100)
arr = []
arr.append(x[0][0])
arr.append(x[0][1][0])
arr.append(x[0][1][1][0])
arr.append(x[0][1][1][1][0])
arr.append(x[0][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
arr.append(x[0][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])
print(arr)

But of course, this is not a professional method.

So, what i want is to know how can i make this one: [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2, 1]

from this one: [(97, (89, (83, (79, (73, (71, (67, (61, (59, (53, (47, (43, (41, (37, (31, (29, (23, (19, (17, (13, (11, (7, (5, (3, (2, (1, None))))))))))))))))))))))))))]

I found the answer here How to flatten a tuple in python but the code there was for python 2, so, i modified it a bit.

and used this code:

def flatten(T):
    if type(T) is not tuple:
        return (T,)
    elif len(T) == 0:
        return ()
    else:
        return flatten(T[0]) + flatten(T[1:])
Dr.venom
  • 48
  • 6
  • 3
    Why does `is_prime` even return a tuple? it should return a boolean – DeepSpace Nov 19 '18 at 20:03
  • you could post process & flatten: https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists and fix your indentation – Jean-François Fabre Nov 19 '18 at 20:04
  • 2
    I don't understand your `is_prime()` function. When `if (x % i) == 0` is true, you know x is not prime, so why do you continue? – John Gordon Nov 19 '18 at 20:05
  • 1
    Also - is there any particular reason to even attempt to use recursion here? It's not necessary and it won't scale. – Jon Clements Nov 19 '18 at 20:06
  • is_prime function will find all prime numbers in a specific range and return all these numbers, it checks if the current value of x is prime, if it is prime it returns this value and calls itself, otherwise it will call itself only without returning the value of x (which should be only prime number). – Dr.venom Nov 19 '18 at 21:01
  • Is there a reason for the nested functions (`is_prime` inside `get_prime`)? Also, `get_primes` would probably be a better name. – Solomon Ucko Nov 19 '18 at 21:09
  • i want the nested function (is_prime()) to check all numbers in the specific range for primality recursively, and return all prime numbers. when they are returned they are put into the list (primes) and then this list is returned to back for initial call, i want it to be a simple list e.g [2,3,5,7] not that list of tuples. – Dr.venom Nov 19 '18 at 21:13

2 Answers2

4

You can adapt your function to be a generator pretty easily:

def is_prime(x):
    if x != 0:
        for i in range(2, int(x)):
            if (x % i) == 0:
                yield from is_prime(x - 1)
                return
        else:
            yield x
            yield from is_prime(x - 1)

Then to get all of the primes up to 100 you can pass that generator to list to get a list containing the values from that generator:

print(list(is_prime(100)))
# [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2, 1]

Recursion isn't a great approach to this though, I would suggest looking up the Sieve of Eratosthenes for a better approach.

The yield from syntax is only available in newer versions of Python (>= 3.3). You can replace 

yield from x

with

for y in x:
    yield y

if necessary.

Patrick Haugh
  • 59,226
  • 13
  • 88
  • 96
  • Thanks for clarification, this is definitely a better way to generate these prime numbers in a specific range, but my question is about how can i get these values out from the returned list: `[(97, (89, (83, (79, (73, (71, (67, (61, (59, (53, (47, (43, (41, (37, (31, (29, (23, (19, (17, (13, (11, (7, (5, (3, (2, (1, None))))))))))))))))))))))))))]` – Dr.venom Nov 19 '18 at 21:19
1

If you create a nested tuple, then the only way to flatten it is by unpacking. Best way to not deal with that is just not creating one. Here goes an alternative version of your code:

def get_primes(limit):

    def is_prime(x):
        if x in (2, 3):
            return True
        if (x % 2 == 0) or (x % 3 == 0):
            return False
        i, w = 5, 2
        while i**2 <= x:
            if x % i == 0:
                return False
            i += w
            w = 6 - w
        return True

    return [x for x in range(2, limit + 1) if is_prime(x)]

print(get_primes(int(input("Enter the range: 0 - "))))
AResem
  • 139
  • 5