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.
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))