Python Challenge - Prime Number Finder

wow! this is hardcore!

Since I hacked that last solution together pretty quickly, here’s one with some comments, a docstring, and a few low-hanging optimizations:

# The data types in the following line are type hints, which generally keep users from inputting invalid args (in addition to also speeding up execution, depending on the python version being used).
def prime_finder(n: int) --> list:
  """
  When given a positive integer as n, `prime_finder()` returns a list of all primes between n and 0.

  Args:
    n (int): A positive integer used as the maximum for the range (i.e., 0 through n) of prime numbers to be found

  Returns:
    found_primes (list): An ordered (smallest-to-largest) list of all prime numbers between n and 0
  """

  # NB: I am *not* a mathematician, so I'm not sure if this assumption is valid, but: I'm assuming that we are only considering *positive* integers for this function; additionally, 1 is not considered prime.  So, for any n less than 2, there are no prime numbers equal to or less than n.  If we *do* want to also consider negative integers, the solution should be trivial (multiply n by -1, then multiply every element of the list by -1 before returning.
  if n < 2:
    return []
  # If we *do* have an n of 2 or greater, then we know there is at least one prime in the list: 2 (the only even prime)!
  else:
    # If n is even (`n % 2 == 0`; 0 is 'false-y', so for an even number, `n % 2` evaluates to `false`) and n is greater than 2, then we want to start not at n (which we *know* is not prime), but at n-1, which will be odd, and therefore has a chance of being prime.
    if not any([n % 2, n == 2):
      n -= 1
    return [
            # Now that we can be sure that n is odd (or 2), we can skip all of the other even numbers between n and 0 by incrementing our range by 2 (instead of the default 1).
            x for x in range(2, n+1, 2)
            # Just as before, where we used the result of a modulo operation directly as the truth-y/false-y outcome, we also use modulo for determining whether or not a given number is prime by looking at the remainder from dividing by each number less than itself; the `all()` function will evaluate lazily, so the first number that divides evenly into x will 'short-circuit' the evaluation (i.e., it returns `false` and moves on to the next x in the comprehension).  NB: I switched the range from its original order (highest to lowest value) to a lowest-to-highest order, as dividing by smaller numbers should be easier and faster (at least I *think* so...)
            if all([x % i for i in range(2, x)])
           ]

print(prime_finder(11))

def prime_finder(n): # Write your code here primes = [] for i in range(2, n+1): include_i = True for p in primes: if i % p == 0: include_i = False break if include_i: primes += [i,] return primes
def prime_finder(n):
  # Write your code here
  prime_list = []

  # Go through each number 'num' from 1 to n inclusive
  for num in range(2, n + 1):
    if num == 2 or num == 3:
      prime_list.append(num)
    else:
      # Check if num is prime
      # num is prime if, for no number 'fac' between 2 and num / 2 (inclusive), num % fac == 0
      pfac = 2
      while pfac <= (int(num / 2)):
        if num % pfac == 0:
          print((num, pfac))
          break
        elif pfac == (int(num / 2)):
          prime_list.append(num)
        pfac += 1
      

  return prime_list

print(prime_finder(20))

I think there’s probably a way to handle the edge cases of 2 and 3 more easily, but I was more interested in the latter part anyways. Main takeaway is that you only have to go up to int(num / 2) to search for factors of num.

def prime_finder(n): my_list = [] for num in range(2, n+1): #for every number from 2 to n+1 [2,3,4,5,6,7,8,9,10,11] is_prime = True #for now this is a prime number (True) for i in range(2, num): #for every number from 2 to num [2,3,4,5] when num=5 if num % i == 0: #if num(e.g 5) is dividable by i (e.g. 3) --> then True is_prime = False #if the above statement is True, then is_prime = False if is_prime == True: my_list.append(num) return my_list print(prime_finder(201)) # Prime can only be divided by 1 and itself #7 --> 2,3,4,5,6 --> F,F,F,F,F --> False, is_prime=True #8 --> 2,3,4,5,6,7 --> T,F,T,F,F,F --> True, is_prime=False
def prime_finder(n): # Write your code here prime = [] for j in range(2,n+1): count =0 for i in range(2,j): if j%i ==0: count =+1 if count == 0: prime.append(j) return prime print(prime_finder(11))
def prime_finder(n): prime_numbers = [] not_primes = [] for x in range(2, n+1): for y in range(2, x): if x % y == 0: not_primes.append(x) if not_primes.count(x)==False: prime_numbers.append(x) return prime_numbers print(prime_finder(11))

def prime_finder(n):
def is_prime(x):
return len([i for i in range(1, x+1) if x%i==0])==2
return [i for i in range(1, n+1) if is_prime(i)]

print(prime_finder(11))

It’s not the most elegant or fanciest solution, but it works.

def prime_finder(n):
  # Prepopulate the results list with the known primes 2 & 3, to solve an edge case
  res = [2, 3]

  for i in range(2, n):
    # adding a testing list to hold the results, to solve other edge cases
    test = []
    for x in range(2, i-1):
      test.append(i % x)
    if 0 not in test:
      # check that the number being tested doesn't already exist in the results list, and adds it if it passes the primes test
      if i not in res:
        res.append(i)
  return res
def prime_finder(n):
    primes = []
    for i in range(1, n+1):
        mod_zero = []
        for j in range(1, i+1):
            if i % j == 0:
                mod_zero.append(j)
        if len(mod_zero) == 2:
            primes.append(j)
        else:
            pass
    return primes
def is_prime(num):
  flag = False
  if num == 1: return None;
  elif num > 1:
    for i in range(2,num):
      if (num % i) == 0:
        flag = True;
        break;
  if flag == False: return num;
  elif flag == True: return None;

def prime_finder(n):
  prime = []
  for i in range(1,n+1):
    if is_prime(i) != None:
      prime.append(is_prime(i))
  return prime
print(prime_finder(11))
1 Like
def prime_finder(n): prime_numbers = [] not_primes = [] for x in range(2, n+1): for y in range(2, x): if x % y == 0: not_primes.append(x) if not_primes.count(x)==False: prime_numbers.append(x) return prime_numbers print(prime_finder(11))

Garfield14 is correct, this code works to find prime numbers up to 11. Thank you, garfield14.

i have try it:

This was my solution.

Typically I would actually just take the helper function, and define it outside the function, to retain reusability.

def prime_finder(n): # Write your code here def find_factors(n): factors = [] for i in range (1, n+1): if (n%i==0): factors.append(i) return factors primes = [] for i in range(1, n+1): f = find_factors(i) if len(f) == 2: primes.append(i) return primes print(prime_finder(11))

I decided to use a counter for how many factors each number has while looping and only appending to my list of primes when those factors numbered two. Since this method requires checking all the numbers in the range I didn’t optimize for speed so I might give this another shot.

def prime_finder(x): primes = [] for n in range(1,x+1): factors = 0 for i in range(1,n+1): if n % i == 0: factors += 1 if factors == 2: primes.append(n) return primes print(prime_finder(11))
1 Like
def prime_finder(n): #List of prime numbers. LOL prime_numbers = [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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] #an empty list / object to return for results prime_list = [] #to iterate all numbers inputnumbers = range(1, n+1) for number in inputnumbers: if number in prime_numbers: prime_list.append(number) else: continue return prime_list print(prime_finder(11))

Did I cheat? I feel bad.

Here’s another try after reading the comment section. lol:

def prime_finder(n): #empty list to store all prime numbers prime_list = [] #iterate through all the inputted number ofcourse #for those who don't know, a prime number must have 2 factors, 1 only has 1. 2 is the smallest number in our list, so we should start at 2 for number in range(2, n+1): #boolean indicator to determine if prime or not, if our current number passed our tests not_prime = False #for each number we are testing, we should iterate all possible factors aside from 1, and itself, for factor in range(2, number): #This is the condition to check if any of our factors are factors of our number. If the number divided by the current factor equals zero, it means it is a factor of that number, therefore, our number is not prime if number%factor == 0: #not_prime is toggled True not_prime = True #Since we already know, we should skip the current loop continue #if not prime, ofcourse, we're not going to append the number to our list if not_prime: continue #If our number is prime, then append the number to our list. If our loop reaches here, it means that any of our factors are not factors of our number. Therefore, it is prime. if not not_prime: prime_list.append(number) return prime_list print(prime_finder(11)) print("\n",prime_finder(110)) print("\n",prime_finder(1023))

Actually liked your code, never thought of doing that since prime numbers only has 2 factors. Really nice logic!

1 Like
def prime_finder(n):
  # Write your code here
  prime_num = []
  for num in range(2, n + 1):
    if num == 2:
      prime_num.append(num)
    elif num > 2:
      is_prime = True
      for i in range(2, num):
        if num % i == 0:
          is_prime = False
          break
      if is_prime:
        prime_num.append(num)
  return prime_num
print(prime_finder(11))

Here is my solution. please review and give your feedback

def prime_finder(n):
  # Write your code here
  p_num = []
  
  while n > 1:
    _range = [num + 1 for num in range(n-1)]
    _range = _range[1:]
    flag = False
    for i in _range:
      if n % i == 0:
        flag = True
        break;
    if flag == False:
      p_num.append(n)
    n -= 1

  return p_num[::-1]
 
print(prime_finder(11))