Python Challenge - Prime Number Finder

def isPrime(n): for i in range(2,n): if n % i == 0: return False return True def prime_finder(n): numbers = list(range(2, n+1)) primes = [] for i in numbers: if isPrime(i): primes.append(i) return primes print(prime_finder(11))

Hey goran_021,

How does 2 get added to the primes list? Obviously 2 % 2 == 0 and 2 % 1 == 0. How do lines 3, 4 and 5 account for that?

I appreciate this isn’t specific to your code but I understood yours the most. Any help would be much appreciated.

Thanks

Hi.

See here :
for i in range(2,n):
if n % i == 0:

If we talk about num 2, then it’s range(2,2), and range from 2 to 2 is none. Because range goes from start(2) to end minus one(2 - 1), and that would be range from 2 to 1 which doesn’t exist so result is none instead of zero you would normally expect.

Take care:)

You are a legend, thank you so much!

1 Like

big code

def prime_finder(n): foo = [] def isComposite(n2): x = [True] for i in range(1, n2 + 1): if n2 % i == 0 and not(i == 1 or i == n2): x.append(False) return not(x[-1]) for i in range(1, n + 1): if not(isComposite(i)) and not(i == 1 or i == 0): foo.append(i) return foo for i2 in range(40): print("{} {}\n".format(i2, prime_finder(i2)))
def prime_finder(n): primes = [] for i in range(2,n+1): print(i) flag = False for x in range(2,i): if flag: continue if i % x == 0: flag = True if not flag: primes.append(i) return primes print(prime_finder(11))

Using list comprehension

def prime_finder(n):
num_list = [num for num in range(2, n+1) if num>1 if all(num % y != 0 for y in range(2, num))]
return num_list

print(prime_finder(11))

from math import factorial def prime_finder(n): # Write your code here primes = [] for nums in range(2, n+1): fact = factorial(nums-1)+1 if fact%nums == 0: primes.append(nums) return primes print(prime_finder(11))

here’s my solution using wilsons’s theorem :slight_smile:

1 Like
def prime_finder(n): # Write your code here def is_prime(m): for j in range(2,m): if m%j == 0: return False return True prime_list = [] for i in range(2, n+1): if is_prime(i): prime_list.append(i) return prime_list print(prime_finder(100))
def prime_finder(n): # Write your code here prime_n = [] for i in range(2,n+1): prime_test = [] for j in range(2,i+1): if i%j == 0: prime_test.append(j) if len(prime_test) == 1: prime_n.append(i) return prime_n print(prime_finder(11))

I ended up using a Sieve of Eratosthenes. It completes in about 12 microseconds for prime_finder(100) according to IPython’s %timeit function:

def prime_finder(n): # Write your code here if n < 2: return [] elif n == 2: return [2] elif n < 5: return [2, 3] # For n above 4, use a sieve of Eratosthenes. RANGE_MAX = n + 1 primes = [True for i in range(RANGE_MAX)] # 0 and 1 are not prime. primes[0] = False primes[1] = False # Set all multiples of 2 to False. for n in range(4, RANGE_MAX, 2): primes[n] = False # Loop through all odd numbers up to the square root of RANGE_MAX. # If the number is prime, set all of its odd multiples to False. for i in range(3, int(RANGE_MAX**0.5) + 1, 2): if primes[i]: for j in range(i*i, RANGE_MAX, i*2): if primes[j]: primes[j] = False # Return the primes using list comprehension. # This is more efficient than appending to a list. return [i for i, prime in enumerate(primes) if prime] print(prime_finder(11)) print(prime_finder(49))

‘’’

1. def prime_finder(n):
2.     if n < 0:
3.         raise ValueError('n must be positive.')
4.     if n < 2:
5.         return []
6.     primes = [2]    
7.     if n == 2:
8.         return primes
9.     # a prime number > 2 must be odd and indivisible by all primes less than it
10.     for i in range(3, n+1,  2):
11.         isprime = True
12.         for j in primes:
13.             if i % j == 0:
14.                 isprime = False
15.         if isprime:
16.             primes.append(i)
17.     return primes
18. print(prime_finder(11))
def prime_finder(n): # Write your code here prime_num = [] # store prime numbers # loop to iterate over values to n for i in range(2,n+1): count = 0 # keep track of evenly divisble values for j in range(2,i): print('i= '+ str(i) + ', j = ', str(j) + ' mod_val = ' + str(i%j)) # if there is any time a divisble is found, add to count and break loop if i % j == 0: count += 1 break if count == 0: prime_num.append(i) return prime_num print(prime_finder(11))

Lots of interesting approaches here. I wanted to find the quickest approach. I used the break method that others above have used. Is there a quicker way to approach this?

def prime_finder(n): list = [] for n in range(1,n+1): if n > 1: for i in range(2,n): if (n % i) == 0: break else: list.append(n) return list print(prime_finder(11))

This is how I solved it.

Not very efficient but gets there eventually :slight_smile:

def find_prime(n): #setting a list where the first number is range[2] of n, since 0 and 1 will never be prime and you can't divide by zero lst = list(range(n + 1)) lst_no_one = lst[2:] almost_prime = [] #iterating through the list twice and appending to almost_prime if the % operation returns 0 for num in lst_no_one: for num2 in lst_no_one: if num % num2 == 0: almost_prime.append(num) #if the number is only one time at the list it is prime, so making a dict to check num frequency dict_prime = {} for num in almost_prime: if num in dict_prime: dict_prime[num] += 1 else: dict_prime[num] = 1 #appending to prime list the keys with value of one prime = [] for key, value in dict_prime.items(): if value == 1: prime.append(key) return prime print(find_prime(10))

Well, that is some elegant code right there… :slight_smile:

def prime_finder(n):

Write your code here

Start with 3 and already add 2 in the list

number = 3

list of prime numbers till “n”

prime_numbers =
prime_numbers.append(2)
while number <= n:
prime = False
test = 2
while test < number:
if number % test == 0:
prime = True
test += 1
if prime == False:
prime_numbers.append(number)
number += 1
return prime_numbers

print(prime_finder(11))

Should have use the break statement!

import math def prime_finder(n): primes = list(range(2, n+1)) print("List to analize : \n", primes, "\n") list_to_analize = [] for i in range(2,n+1): list_to_analize = list(range(2, math.ceil(i/2)+1)) print("Analizing ", i, "with ", list_to_analize) for j in range(2, math.ceil(i/2)+1): print("dividing ", i ,"with ", j) if i%j == 0 and i != j: print("Removing ", i) primes.remove(i) break print("primes after this iteration ", primes, "\n") return primes print(prime_finder(11))
def is_prime(n): if (n <= 3) : return "Prime" for i in range(2, n+1 // 2): if n % i == 0: return "Not Prime" else: return "Prime" def prime_finder(n): # Write your code here if n > 1: results = [] for i in range(2, n+1): if is_prime(i) == "Prime": results.append(i) return results print(prime_finder(11))