Hey, I had a question about your code. I’m having trouble understanding lines 5 and 6. I get that you’re taking i and finding the remainder after dividing j into. How is it that when you iterate through i and j you aren’t always getting the same numbers for i and j? (I’m not sure if I explained that well) What I mean is why isn’t always like 1 % 1, 2 % 2, and so on?
Hi I was wondering what the p = False, P= True and if p do in your code.
def prime_finder(n):
if n < 2:
return None
else:
ls=[]
for i in range(2,n+1):
x = 2
c = 0
while x < i :
if i % x == 0:
c +=1
x +=1
if c == 0:
ls.append(i)
return ls
print(prime_finder(11))
My approach is to find the numbers that are not primes first as this is easier than finding primes.
Then return a range of numbers up to n and minus the numbers that are not primes.
def prime_finder(n):
not_primes=[]
for i in range(2, n+1):
for j in range(2, i+1):
if j!= i and i % j == 0:
not_primes.append(i)
primes= [x for x in range(2, n+1) if x not in not_primes]
return primes
1 Like
- Test for positive integer input
- Define function i
s_prime(number)to test if a number is prime - Loop, checking each number
(2, n+1)inis_prime(), appending primes to list - Output list
import sys
def prime_finder(n):
# Write your code here
if n <= 1 or type(n) != int:
print("Enter a positive integer")
sys.exit()
primes = []
def is_prime(number):
prime = True
for i in range(2, number):
if number % i == 0:
prime = False
return prime
for j in range(2, n+1):
if is_prime(j):
primes.append(j)
return primes
print(prime_finder(113))
As above my approach was finding the non primes and using the break keyword when that was achieved.
I had to go back and adjust the n range to exclude 1.
def prime_finder(n):
my_list = []
for n in range(2, n + 1):
for x in range(1, n):
if x != n and n % x == 0 and x != 1:
break
else:
my_list.append(n)
return my_list
print(prime_finder(11))
def prime_finder(n):
def is_prime(num):
factors = 0
for i in range(1, int(num / 2) + 1):
if(num % i == 0): factors += 1
if factors == 1: return True
elif factors > 1: return False
return [x for x in range(1, n + 1) if is_prime(x)]
print(prime_finder(11))
1 Like
- The “j” loop checks if the number is prime where “m” value needs to be 2;
- The “i” loop runs to the next number to be checked (decreasing);
- “lista” stores the primes;
- lista.sort() arranges the numbers in ascending order.
def prime_finder(n):
lista = []
for i in range(n, 1, -1):
m=0
for j in range(1, i+1, 1):
num = i%j
if num==0:
m += 1
if m == 2:
lista.append(j)
lista.sort()
return(lista)
print(prime_finder(11))
def prime_finder(n):
list = [x for x in range(2,n+1)]
for x in range(1,n+1):
for y in range(1,x+1):
if y != 1 and y != x:
if x % y == 0:
try: list.remove(x)
except ValueError: pass
return list
print(prime_finder(11))
def prime_finder(n):
primes=[]
for i in range(2, n+1):
for j in range(1, i):
if (i % j) == 0 and j != 1:
break
elif j == i-1:
primes.append(i)
return primes
print(prime_finder(11))
def prime_finder(n):
# Write your code here
asdlkj= []
if n == 0 or n==1:
return asdlkj
for i in range (2,n+1):
if i % 2 == 0:
if i==2:
asdlkj.append(i)
elif i% 3== 0:
if i==3:
asdlkj.append(i)
elif i% 5== 0:
if i==5:
asdlkj.append(i)
elif i% 7== 0:
if i==7:
asdlkj.append(i)
else:
asdlkj.append(i)
return asdlkj
print(prime_finder(11))
i made a one-liner prime finder for fun. i don’t recommend anyone code this way:
(oh, and these solutions work for negatives, zero, and one, as well—returning an empty list)
def one_line_primes(n):
return [] if n < 2 else [2] + [n for n in range(3, n+1, 2) if all(n % i for i in range(3, int(n**(1/2))+1, 2))]
this is roughly equivalent to the below code. the only difference is i used all(n % i ...). this (inefficiently) checks against all odd numbers up to the square root. it’s better to save a list of previously encountered primes, but with one line of code, i couldn’t figure out a way to initialize and populate a list of primes to check against. in two lines of code, that may be doable using the walrus operator :=
# Inspect only odds; two is the only even prime
# Inspect only up to sqrt n; after sqrt n, you're checking duplicate factors
# Checks against all odd numbers
def prime_finder_odds(n):
return [] if n < 2 else [2] + [n for n in range(3, n+1, 2) if is_prime(n)]
def is_prime(n):
for i in range(3, int(n**(1/2))+1, 2):
if not n % i:
return False
return True
i also did this two-liner, which is better than the previous one because it only checks the previously encountered primes:
def two_line_primes(n):
primes = []
return [] if n < 2 else [2] + [(n_, primes.append(n_))[0] for n_ in range(3, n+1, 2) if all(n_ % prime for prime in [prime for prime in primes if prime <= n_**(1/2)])]
this is based on these lines. this version works better because it breaks out of loops early, whereas the two-line version uses comprehensions, which can’t stop early. and the above version recomputes the root every iteration. the below version doesn’t.
def prime_finder_procedural(n):
primes = []
if n < 2:
return []
for n_ in range(3, n+1, 2):
root = n_ ** (1/2)
for prime in (prime for prime in primes if prime <= root):
if not n_ % prime:
break
else:
primes.append(n_)
return [2] + primes
for this one what u have to do is first check if n is 0 or 1 because if it is then the list will pretty much be nothing so if it is then return an empty list
if not then you have to make a for loop starting from 2 to n+1 and you might be thinking “why n+1 why not just n” well its because if you do just n then it will stop at n and not check for it so it has to be n+1
so the for loop basically checks if i is a modulo of a prime number and if it is then it checks if i is the prime number for example if i is 2 then it will first check if i%2 = 0, it is so it then checks if i = 2 and since it is it adds 2 to the prime number list
so then it loops and checks this for all of the prime numbers, btw if it is not a modulo of any of the single digit prime numbers (2, 3, 5, and 7) then that means it doesn’t have any factors so it adds it to the prime number list
so after its done checking all the numbers it returns the list of the prime numbers
def mark_multiples(i, list):
n = list[i]
if n != -1:
for j in range(i+n, len(list), n):
list[j] = -1
"""
Done by sieve of Eratosthenes
(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes):
Assume that every number
[1:n] is prime, then remove
the multiples of each number,
beginning with the first
prime number 2, then 3,
not 4 (because it was already
removed), etc. The remaining
numbers are all prime
numbers from 1 to n.
"""
def prime_finder(n):
numbers = list(range(2, n+1))
"""
It suffices to check for multiples
of [2:sqrt(n) - 1] because every
non-prime number in [sqrt(n):]
contains prime factors in [2:sqrt(n) - 1]
"""
for i in range(int(len(numbers)**0.5 - 1)):
mark_multiples(i, numbers)
numbers.sort()
primes = numbers[numbers.index(2):]
return primes
print(prime_finder(11))
very nice. the sieve of eratosthenes can also be done without the sort and index. here’s another version that is faster that uses a boolean mask.
def eratosthenes(limit):
primes = [2]
sieve = [True] * limit
for i in range(3, limit, 2): # Use odds to halve search
if sieve[i]:
primes.append(i)
for j in range(i*i, limit, 2*i): # Start from the square
sieve[j] = False
return primes
although these sieves are much quicker than brute force approaches, they are memory expensive. i’ve read there are ways of splitting the sieve into pieces . . .
1 Like
Interesting, thanks for the reply. Excluding even numbers !=2 from the search a priori makes perfect sense as a quick hack to half the search range. Using booleans instead of integers in the sieve however just makes a minor difference in memory usage, doesn’t it? (If Python even uses memory that efficiently?!)
The marking & sorting was just the first thing I came up with to do the search in-place. There are probably better solutions. But I figured, sorting can be done in O(n*log n) and cutting off the first part of list in O(1) which seemed fast enough to me. In your sieve you create a new list instead of modifying an existing one which means basically you trade off computation time for used memory, right? Then again, your boolean mask is probably not using that much memory so that might balance it out?! Hm.
I’m not that proficient in Python, is there an easy way to compare memory usage of two programs? I read using libraries like psutil isn’t as straightforward as one would think…
1 Like
finding primes, I tought this was pretty quick with a generator.
def prime_finder(n):
# Write your code here
lst_prime = []
for i in range(1, n+1):
lst = [ i for x in range(n, 1, -1) if i % x == 0]
if len(lst) == 1:
lst_prime.append(lst[0])
return lst_prime
print(prime_finder(11))
def is_prime(n):
# create list of 2 to n values (excludes n)
list_n = list(range(2, n))
# if n is divisible by any number from 2 to n-1, return False
for i in list_n:
if n % i == 0:
return False
return True
def prime_finder(n):
# create list of primes
primes = [i for i in range(3, n+1) if is_prime(i)==True]
# insert 2 into beginning of list
primes.insert(0, 2)
return primes
print(prime_finder(100))
Just so you know, since when you define a range, the second argument is exclusive, you don’t need the x!= n in line 5 since n isn’t in your range. 