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