CODEWITHSUNDEEP
pythonprimes
WhyDoYouCare
WhyDoYouCare

Reputation: 9

Break in Boolean Loops

I don't know what I am doing wrong for a challenge: I need to find prime numbers in a list nums and return them in a new list. Can someone help me!? My answer solution is below.

def find_primes(nums):
  
    lst = []
    prime = False
    for pr in range(2, nums + 1):
        prime = True
    
    for num in range(2, pr):
        if pr % num == 0:
            prime = False
            break
    
    if prime:
        lst.append(pr)
        
    return(lst)

Upvotes: 0

Views: 285

Answers (4)

Tahil Bansal
Tahil Bansal

Reputation: 163

There were some mistakes. Here's the corrected code:

def prime_number(nums):
lst= nums
lst2=[]

for pr in range(0,len(lst)):
    if lst[pr]>1:
        flag = 0
        for i in range(2,lst[pr]-1):
            if (lst[pr]%i)==0:
                flag=1
                break

        if(flag==0):
            lst2.append(lst[pr])

return lst2

list=[3,10,7,17,6,45,13]
prime_list= prime_number(list)
print(prime_list)

Upvotes: -1

user140242
user140242

Reputation: 179

You can use the sieve of Eratosthenes

def find_primes(nums): 
    lst = [] 
    prime = [True] * (nums+1)
    for i in range(2, nums + 1): 
        if prime[i]:
            lst.append(i) 
            if i*i<=nums:
                prime[i*i::i]=[False]*((nums-i*i)//i+1)
    return(lst)

Upvotes: 1

Arty
Arty

Reputation: 16747

I provided your algorithm find_primes() with minimal corrections to make it work, the only problem you had is wrong indentations (wrong number of spaces at starts of lines).

And I implemented a faster version find_primes2() that checks until square root of number and only odds.

And then even more faster version find_primes3() that checks until square root and checks only divisors from current prime list.

Try it online!

def find_primes(nums):
    lst = []
    for pr in range(2, nums + 1):
        prime = True

        for num in range(2, pr):
            if pr % num == 0:
                prime = False
                break

        if prime:
            lst.append(pr)
            
    return(lst)

print(find_primes(123))

def find_primes2(nums):
    import math
    if nums < 2:
        return []
    lst = []
    for pr in range(3, nums + 1, 2):
        prime = True

        for num in range(3, math.floor(math.sqrt(pr) + 0.1) + 1, 2):
            if pr % num == 0:
                prime = False
                break

        if prime:
            lst.append(pr)
            
    return([2] + lst)

print(find_primes2(123))

def find_primes3(nums):
    import math
    if nums < 2:
        return []
    lst = [2]
    for pr in range(3, nums + 1, 2):
        prime = True

        limit = math.floor(math.sqrt(pr) + 0.1)
        for num in lst:
            if num > limit:
                break
            if pr % num == 0:
                prime = False
                break

        if prime:
            lst.append(pr)
            
    return(lst)

print(find_primes3(123))

Output:

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

Upvotes: 0

Arun Kaliraja Baskaran
Arun Kaliraja Baskaran

Reputation: 1086

A more pythonic way or implementing this would be to use the filter function provided by python..

In [6]: def isPrime(num):
   ...:     if num < 2:
   ...:         return False
   ...:     for x in range(2, num):
   ...:         if num % x == 0:
   ...:             return False
   ...:     else:
   ...:         return True
   ...:

In [7]: nums =  list(range(1, 100))

In [9]: list(filter(isPrime, nums))
Out[9]:

NOTE: The else inside the isPrime function is for the for loop

Upvotes: 1

Related Questions