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
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):
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))
Garfield14 is correct, this code works to find prime numbers up to 11. Thank you, garfield14.
This was my solution.
Typically I would actually just take the helper function, and define it outside the function, to retain reusability.
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.
Did I cheat? I feel bad.
Here’s another try after reading the comment section. lol:
Actually liked your code, never thought of doing that since prime numbers only has 2 factors. Really nice logic!
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))