# Python Challenge - Prime Number Finder

``````def prime_finder(n):
t = [i for i in range(2,n+1)]
for i in t:
for j in t:
if (j % i == 0) & (j != i) & (i >= 2):
t.remove(j)
return t

print(prime_finder(11))
``````
1 Like

I used memoization to convert time complexity to space complexity.

import time IS_PRIME_DICT = { # int : bool } def prime_finder(n): # Write your code here primes = [] for i in range(2, n + 1): if is_prime(i): primes.append(i) return primes def is_prime(x): # memoization global IS_PRIME_DICT if x in IS_PRIME_DICT: return IS_PRIME_DICT[x] # compute if necessary for i in range(2, x): if x % i == 0: IS_PRIME_DICT[x] = False return False IS_PRIME_DICT[x] = True return True # O(n^2) time without memoization # O(1) space complexity # O(n) time with memoization (if memoized) # O(n) space complexity
def prime_finder(n): num_list = list(range(1, n+1, 1)) prime_list = [] print("Out of this list of numbers: ", num_list) i = 0 while i < n: counter = 0 x = n - i y = n - i while x >= 1: if (y % x) == 0: counter += 1 x -= 1 if counter == 2: prime_list.insert(0, y) i += 1 print("These are the prime numbers:", prime_list) return prime_list prime_finder(11)
def prime_finder(n): primes = [] for i in range(2, n+1): if i <= 3: primes.append(i) else: for j in primes: if i % j == 0: break else: primes.append(i) final = [] for i in primes: if i not in final: final.append(i) return final print(prime_finder(11))

In my solution I didn’t use a factor list at all because if even a single factor beyond 1, and the candidate prime itself is found then we automatically know it’s not a prime number. So we break the factor loop for that candidate prime and move on to the next. We also know that if the inner loop ever finishes without breaking it’s because it didn’t find a 3rd factor, therefore the number is prime. Good luck to everyone on their coding journey!

def prime_finder(n): #We already know 2 is prime. So we add it to the list to simplify the code. prime_list = [2] #Start i at 3 because we know 0 and 1 aren't prime, and we already know 2 is. i = 3 for i in range(n + 1): #i is the candidate prime starting at 3 remainder = i % 2 if remainder is 0: continue #start the for loop at 2 because we know 1 is already a factor. We also dont need to check i, because we know it's already a factor. #factor_list = [1, i] for j in range(2, i): remainder = i % j if remainder is 0: #factor_list.append(j) break else: if j == (i - 1): prime_list.append(i) else: continue return prime_list print(prime_finder(97))
def prime_finder(n): p = list(range(2, n +1)) l = [] t = [] for num in p: for i in list(range(2, num)): if (num % i) == 0: break else: t.append(num) return t print(prime_finder(11))
def prime_finder(n): # Write your code here prime_number = [] for num in range(2, n+1): for i in range(2, num): if num % i == 0: break else: prime_number.append(num) return prime_number print(prime_finder(11))
def prime_finder(n): primes=[2] for j in range(3, n+1): div=0 for k in primes: if j%k == 0: div+=1 break if div==0: next_prime=j primes.append(next_prime) return primes print(prime_finder(69420))
def prime_finder(n): # Write your code here primes = [] for number in range(n+1): if number > 1: for _ in range(2, number): if number % _ == 0: break else: primes.append(number) return(primes) print(prime_finder(11))
def prime_finder(n): # Write your code here primes_list = [] for i in range(2, n+1): remainders = [] for j in range(2, i+1): remainders.append(i%j) if remainders.count(0) <= 1: primes_list.append(i) return primes_list print(prime_finder(11)) print(prime_finder(5)) print(prime_finder(43)) print(prime_finder(27))
def prime_finder(n): #define an empty prime number array primes = [] #for each number up to n for i in range(2, n + 1): modulos = [i%p for p in primes] zero_count = modulos.count(0) #if there is at least one 0, i is not a prime if zero_count > 0: continue #if there are no 0, i is a prime, add to the list else: primes.append(i) #return the list of prime numbers return primes print(prime_finder(11))`Preformatted text`
def prime_finder(n): # Write your code here prime_numbers = [] for i in range(2,n+1): prime = True for j in range(2,i): if i % j == 0: prime = False break if prime: prime_numbers.append(i) return prime_numbers print(prime_finder(11))

This is the first time I do the Prime Number Finder on Python; I have used other languages before.
On the isPrime function, I first identify non-prime number to eliminate; if the number modulo the iteration equals zero but the iteration does not equal the number, it is a good indication that it is not a prime number; the code then breaks; otherwise, it would be a prime number.

def isPrime(n): for i in range(2,n+1): if n%i==0 and i!=n: break if n%i==0 and i==n: return True def prime_finder(n): newlist = [x for x in range(2,n+1) if isPrime(x) ] print(newlist) prime_finder(11)

Hi all,

I completed this challenge (with some youtube assistance on the prime algorithm). I wanted to know if someone could perform a quick code review and provide any recommendations on how this could be improved. Thanks!!

``````
def is_prime(num):
if num == 1 or num == 0:
return False
else:
for i in range(2,num):
if num % i == 0:
return False
break
else:
return True
def prime_finder(n):
listofnums = []
for i in range(n+1):
if is_prime(i) == True:
listofnums.append(i)
return listofnums

print(prime_finder(11))
``````

I completed this challenge by cancelling multiples of 2,3,4,5,6 and 7
I’m sure there must be a more efficient way, nonetheless it worked

``````def prime_finder(n):
prime_nums = []
for n in range(2,n+1):
if n == 2 or n ==3 or n == 5 or n == 7:
prime_nums.append(n)
if n%2 != 0 and n%3 != 0 and n%4 != 0 and n%5 != 0 and n%6 !=0 and n%7 != 0 and n not in prime_nums:
prime_nums.append(n)
print(prime_nums)
return(prime_nums)

prime_finder(11)
prime_finder(200)
``````

We will never knock invention, ingenuity and initiative, so your less efficient way is cool with us. Your admission of acceptance that there may be a more efficient way is the first step in working toward it. Accept that our code is not perfect is always the best place to start. Kudos.

I would definitely want to take that code back to the drawing board and look for ways to apply the principle of it without all the excessive logic. It can be done, and in all fairness, I’ll leave that to you.

I think one simple solution is to assume that the number is a prime and then test if it isn’t. If that’s the case, remove it from the list. Here is my solution:

``````def prime_finder(n):
# define empty list to store primes:
out = []
# loop over each number in the range:
for x in range(1, n+1):
# assume it is prime:
out.append(x)
for y in range(2, x):
# if it is not prime, get out of the list
if x % y == 0:
out.pop()
break
# remove 1 because it is not prime
out.remove(1)
return out
``````
def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True def prime_finder(n): prime_list = [] # Write your code here for i in range(1,n+1,1): if is_prime(i): prime_list.append(i) return prime_list print(prime_finder(39))

Hi there, I just wanted to add a little bit to your solution. I’ve tested it alongside my solution and found out that for 2nd test: prime_finder(200) yours include some numbers that are not actually prime numbers: your solution returned a list of 50 numbers, mine - a list of 46 numbers. Upon closer inspection I realised your solution does not account for the fact that 121, 143, 169, 187 are not prime numbers. That happend because the code hasn’t accounted for multiples of 11, 13, 17 etc. The longer the range, the more chance will be that some multiples haven’t been accounted for.

1 Like

My basic solution

def prime_finder(n): # Write your code here primes = [] for number in range(2,n+1): divisores = 2 for divisor in range(2,number): if number%divisor == 0: divisores+=1 if divisores ==2: primes.append(number) return primes print(prime_finder(37))