def prime_finder(n):
prime_list =
for i in range(2,n+1):
for j in range(2,i+1):
if i%j == 0 and i != j:
break
else:
continue
if i == j:
prime_list.append(i)
return prime_list
print(prime_finder(23))
def isPrime(n)->bool:
if n <= 3:
return n > 1
if not n%2 or not n%3:
return False
i = 5
stop = int(n**0.5)
while i <= stop:
if not n%i or not n%(i + 2):
return False
i += 6
return True
def prime_finder(n):
primes = []
for i in range(2,n+1):
if isPrime(i):
primes.append(i)
return primes
print(prime_finder(11))
def prime_finder(num):
prime_numbers = []
for n in range(2,num+1):
c = 0
for i in range(1,n):
if n%i == 0:
c += 1
if c == 1:
prime_numbers.append(n)
return prime_numbers
print(prime_finder(11))
def prime_finder(n):
Write your code here
l = []
for num in range(1,n+1):
c = 0
for i in range(2,(num//2 + 1)):
if num%i==0 :
c = c + 1
break
if c==0 and num!=1:
l.append(num)
return l
print(prime_finder(11))
def prime_finder(n):
ls = [ x for x in range(2,n+1)]
primes = []
while len(ls) > 0:
primes.append(ls[0])
ls = [ x for x in ls if x % ls[0] != 0]
return primes
print(prime_finder(11))
Sieve of Eratosthenes
def prime_finder(n):
numbers = range(2,n+1)
prime_numbers = []
for num in numbers:
count = 0
for i in range(2,num):
if num % i == 0:
count += 1
if count == 0:
prime_numbers.append(num)
return prime_numbers
print(prime_finder(11))
A Prime finder is especially useful if subsequent uses are given the advantage of previous results in the form of a memoized data set. In other words, each run of the function starts with a stored data set upon which only newly generated values will have the expenditure of the brute force algorithm implemented to produce the next prime. Any furtherance of this data set will always have a store for future queries.
Hint: Use a tuple, not a list. We would not want any chance of corruption.
Consider,
>>> t = 1, 2, 3, 4
>>> t = *t, 5
>>> t
(1, 2, 3, 4, 5)
>>>
We call it the, plus-equals for tuples. Only thing it is actual reassignment, not augmented assignment.
Your function will need to know when it has run out of candidates and need to start generating its own, which will be added to the store as found. This is the algorithm I would love to see a student produce. No, I’m not being facetious, only encouraging a little theatre. I know it can be done. Who will show us their attempt at it?
I couldn’t think of a better runtime solution to this problem than O(n^2). I nested loops (in this case while-loops, but for-loops can be easily substituted) to compare a number against lesser numbers to check if any are other factors.
def prime_finder(n):
#will break the moment number is proved not prime
list_of_primes =
test_number = 2
#-> loop to go through numbers in desired range
#(n+1 indicating inclusivity)
while test_number < n+1:
#-> loop to check factors against numbers
#-> can omit 1 and itself (every number is divisible
#by 1 and itself)
factor = 2
while factor < test_number:
if test_number % factor == 0:
break
factor += 1
#-> loop completed and never broke, so only
#divisible by 1 and itself
if factor == test_number:
list_of_primes.append(test_number)
test_number += 1
return list_of_primes
print(prime_finder(11))
here’s a version of the using that memoization stuff … but it would not pass the challenge’s requirements
from math import sqrt
list_of_primes = []
def isPrime(n):
if n in list_of_primes:
return True
x = 2
length = len(list_of_primes)
j = 0
while(x <= sqrt(n) and j < length):
x = list_of_primes[j]
if (n % x) == 0:
return False
j += 1
return True
def prime_finder(n):
if (n < 0):
n = n * -1
if (n < 2):
return []
if ((len(list_of_primes) == 0) or (n >= list_of_primes[-1])):
start = 2
if ((len(list_of_primes) > 0) and (list_of_primes[-1] > 2)):
start = list_of_primes[-1] + 1
for i in range(start, n + 1):
if (isPrime(i)):
list_of_primes.append(i)
return list_of_primes.copy()
else: #(n < list_of_primes[-1]):
i = 0
while(list_of_primes[i] <= n):
i += 1
return list_of_primes[: i]
print(prime_finder(11))
print(prime_finder(21))
print(prime_finder(7))
Copy that. It’s a supplemental challenge in this regard, fwiw.
The hint said to use a tuple, remember?
primes = 2, 3, 5, 7
The seed tuple which is all we need to find primes under 50.
In that exploration, once we have all those primes…
... 41, 43, 47
we can find all the primes less than 2207.
One can see why storing this tuple of primes is of such significant value as the numbers get larger. The tuple is always ahead of them.
I tried to modify the previous code to use a tuple instead of a list:
from math import sqrt
tuple_of_primes = (2, 3, 5, 7) #tuple()
def isPrime(n):
if n in tuple_of_primes:
return True
x = 2
length = len(tuple_of_primes)
j = 0
while(x <= sqrt(n) and j < length):
x = tuple_of_primes[j]
if (n % x) == 0:
return False
j += 1
return True
def prime_finder(n):
if (n < 0):
n = n * -1
if (n < 2):
return []
global tuple_of_primes
if ((len(tuple_of_primes) == 0) or (n >= tuple_of_primes[-1])):
start = 2
if ((len(tuple_of_primes) > 0) and (tuple_of_primes[-1] > 2)):
start = tuple_of_primes[-1] + 1
for i in range(start, n + 1):
if (isPrime(i)):
tuple_of_primes = (*tuple_of_primes, i)
return tuple_of_primes
else: #(n < tuple_of_primes[-1]):
i = 0
while(tuple_of_primes[i] <= n):
i += 1
return tuple_of_primes[:i]
print(prime_finder(11))
print(prime_finder(21))
print(prime_finder(3))
Don’t think of lists. Study the splat syntax from the previous ‘lecture’.
Lists have too much overhead to be viable data structures.
Thank you for bringing this to my attention. My code was bogged-down with multi-line comments. However, I didn’t anticipate it would look so terrible as text, given it looked good in the workspace; perhaps it was the highlighted text that brightened the appearance. Once again, thank you.
1 Like
Just look in to how Markdown can help you to post code so we see what you see.
def prime_finder(n):
Write your code here
my_list=
for i in range(2,n+1):
check = 1
for j in range(2,i):
if i%j==0:
check=0
break
if check==1:
print(i)
my_list.append(i)
return my_list
print(prime_finder(11))
def prime_finder(n):
# Write your code here
array = []
def is_prime(x):
i=int(x/2)
while i>1:
if x%i==0:
return False
i=i-1
return True
for y in range(2,n+1):
if is_prime(y):
array.append(y)
return array
print(prime_finder(11))
def prime_finder(n):
# Write your code here
prime = []
for num in range(1, n + 1):
check = []
for div in range(1, num + 1):
i = num / div
if i - int(i) == 0 and i not in check:
check.append(i)
if len(check) == 2:
prime.append(num)
return prime
print(prime_finder(11))
def prime_finder(n):
# Write your code here
primes = []
for i in reversed(range(2,n+1)):
count = 0
halfway = int(i/2)
for j in reversed(range(2,halfway+1)):
if(i%j==0):
count +=1
if(count==0):
primes.append(i)
primes.sort()
return primes
print(prime_finder(11))