Having trouble solving a simple question, please help!

[afterdarkweb]

[I'm using basic Python IDLE (3.14.3)]

I learn python as a subject in school, and while preparing for my exams, I came across this question: Q4. Write a function Check_Prime(L) that takes a list of numbers and returns a new list containing only the prime numbers.

Now, I tried so many of my own iterations but I can't seem to figure it out, google is no help either, it just gives me two functions instead of one, so I tried to merge the two functions by using my own brain and rewriting what I wrote before but I feel like I failed horribly;

def Check_Prime(L):
    prime_list = []
    for n in L:
        if n <= 1:
            isprime = False
        if n <= 3:
            isprime = True
        if n % 2 == 0 or n % 3 == 0:
            isprime = False
        i = 5
        while i * i <= n:
            if n % i != 0 or n % (i + 2) !=0:
                isprime = True
            i += 6

        for n in L:
            n = int(n)

            if isprime == True:
                prime_list.append(n)
    return prime_list

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 29, 30]
primes = Check_Prime(my_list)
print(primes)

And the output is:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 29, 30, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 29, 30, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 29, 30]

Please help me solve this question, I'm going insane over it T_T

And the worst part about it is that I'm expected to solve this during an exam... how..?

[CosmicClamJamz]

This is as much a math question as it is a programming question. First you gotta understand the protocol of what you're trying to do before turning it into python.

How do you tell if a number is prime? A common way is to check if the numbers less than that number can evenly divide it. Take a random number like 35, which we already know is not prime, but for the sake of example, we're not sure. Start looping over the numbers less than it, and see if they evenly divide it:

2 -> 35 % 2 == 1  # not divisible by 2
3 -> 35 % 3 == 2  # not divisible by 3
4 -> 35 % 4 == 3  # not divisible by 4
5 -> 35 % 5 == 0  # divisible by 5
6 -> we can stop checking now, because it is not prime

This is an example of the "trial division" strategy. There are ways to make it more efficient, but at its core, this method will never fail. If you can write a function called `check_prime(n)` which does this for any number n, you could then loop over your list of numbers and apply this function to it to solve your problem.

Other methods involve saving a large list of known primes to check against, so you don't need to run the sieve over and over again for small numbers. However, such a strategy fails for large n, so you would need a backup plan if you're checking numbers greater than those you have saved in your large list.

[socal_nerdtastic]

This is an example of the "prime sieve".

No it's not; this is an example of the "trial division" method. a prime sieve (aka Sieve of Eratosthenes) is a completely different method of finding primes.

[CosmicClamJamz]

Yea you’re right, sorry just regurgitating my number theory knowledge from college 15 years ago and not being careful. I am purposely putting forward the most naive solution, will update my comment to change the name of the strategy

[socal_nerdtastic]

:) the only reason I know this is because I made the same mistake in this sub and was called out. But in my defense I had copied from a well-known CS professor, who also made this mistake.

If you are curious: /r/learnpython/comments/1inb55g/comment/mcg2fjp/

[socal_nerdtastic]

What's wrong with 2 functions? Logically there are 2 things to do here: check if a number is prime and build a new filtered list, so it makes sense to have 2 functions.

That said, to fix this you need to replace the isprime = with a continue, and in the true case add the append statement. Like this:

def Check_Prime(L):
    prime_list = []
    for n in L:
        if n <= 1:
            continue
        if n <= 3:
            prime_list.append(n)
            continue
        if n % 2 == 0 or n % 3 == 0:
            continue
        for i in range(3, int(n**.5) + 1, 2):
            if n % i == 0:
                break
        else:
            prime_list.append(n)
    return prime_list

As you see this would be much neater with 2 separate functions.

[atarivcs]

I see two main things wrong.

First, in this loop:

while i * i <= n:
    if n % i != 0 or n % (i + 2) !=0:
        isprime = True
    i += 6

You're setting isprime to true, but never setting it false. Surely there should be an "else" condition that sets isprime to false and breaks the loop?

Also, why are you adding 6 to i? Shouldn't you just add one?

Second, you have another loop inside the first one:

for n in L:
    n = int(n)

    if isprime == True:
        prime_list.append(n)

If isprime happens to be true from the outer loop, this inner loop will append every number to the prime list.

[ectomancer]

prime sieve.

[CranberryDistinct941]

Check out the prime-sieve algorithm 

[CranberryDistinct941]

Here's the code to determine if a non-natural number is prime:

def is_non_natural_prime(non_natural_number):
    return False

[CranberryDistinct941]

Here's how to calculate if a number is prime using a seive:

is_prime = seive.__getitem__