def prime_finder(n):
# Write your code here
t = [i for i in range(2,n+1)]
for i in t:
for j in t:
if (j % i == 0) & (j != i) & (i >= 2):
t.remove(j)
return t
print(prime_finder(11))
1 Like
I used memoization to convert time complexity to space complexity.
import time
IS_PRIME_DICT = {
# int : bool
}
def prime_finder(n):
# Write your code here
primes = []
for i in range(2, n + 1):
if is_prime(i):
primes.append(i)
return primes
def is_prime(x):
# memoization
global IS_PRIME_DICT
if x in IS_PRIME_DICT:
return IS_PRIME_DICT[x]
# compute if necessary
for i in range(2, x):
if x % i == 0:
IS_PRIME_DICT[x] = False
return False
IS_PRIME_DICT[x] = True
return True
# O(n^2) time without memoization
# O(1) space complexity
# O(n) time with memoization (if memoized)
# O(n) space complexity
def prime_finder(n):
num_list = list(range(1, n+1, 1))
prime_list = []
print("Out of this list of numbers: ", num_list)
i = 0
while i < n:
counter = 0
x = n - i
y = n - i
while x >= 1:
if (y % x) == 0:
counter += 1
x -= 1
if counter == 2:
prime_list.insert(0, y)
i += 1
print("These are the prime numbers:", prime_list)
return prime_list
prime_finder(11)
def prime_finder(n):
primes = []
for i in range(2, n+1):
if i <= 3:
primes.append(i)
else:
for j in primes:
if i % j == 0:
break
else:
primes.append(i)
final = []
for i in primes:
if i not in final:
final.append(i)
return final
print(prime_finder(11))
In my solution I didn’t use a factor list at all because if even a single factor beyond 1, and the candidate prime itself is found then we automatically know it’s not a prime number. So we break the factor loop for that candidate prime and move on to the next. We also know that if the inner loop ever finishes without breaking it’s because it didn’t find a 3rd factor, therefore the number is prime. Good luck to everyone on their coding journey!
def prime_finder(n):
#We already know 2 is prime. So we add it to the list to simplify the code.
prime_list = [2]
#Start i at 3 because we know 0 and 1 aren't prime, and we already know 2 is.
i = 3
for i in range(n + 1):
#i is the candidate prime starting at 3
remainder = i % 2
if remainder is 0:
continue
#start the for loop at 2 because we know 1 is already a factor. We also dont need to check i, because we know it's already a factor.
#factor_list = [1, i]
for j in range(2, i):
remainder = i % j
if remainder is 0:
#factor_list.append(j)
break
else:
if j == (i - 1):
prime_list.append(i)
else:
continue
return prime_list
print(prime_finder(97))
def prime_finder(n):
p = list(range(2, n +1))
l = []
t = []
for num in p:
for i in list(range(2, num)):
if (num % i) == 0:
break
else:
t.append(num)
return t
print(prime_finder(11))
def prime_finder(n):
# Write your code here
prime_number = []
for num in range(2, n+1):
for i in range(2, num):
if num % i == 0:
break
else:
prime_number.append(num)
return prime_number
print(prime_finder(11))
def prime_finder(n):
primes=[2]
for j in range(3, n+1):
div=0
for k in primes:
if j%k == 0:
div+=1
break
if div==0:
next_prime=j
primes.append(next_prime)
return primes
print(prime_finder(69420))
def prime_finder(n):
# Write your code here
primes = []
for number in range(n+1):
if number > 1:
for _ in range(2, number):
if number % _ == 0:
break
else:
primes.append(number)
return(primes)
print(prime_finder(11))
def prime_finder(n):
# Write your code here
primes_list = []
for i in range(2, n+1):
remainders = []
for j in range(2, i+1):
remainders.append(i%j)
if remainders.count(0) <= 1:
primes_list.append(i)
return primes_list
print(prime_finder(11))
print(prime_finder(5))
print(prime_finder(43))
print(prime_finder(27))
def prime_finder(n):
#define an empty prime number array
primes = []
#for each number up to n
for i in range(2, n + 1):
modulos = [i%p for p in primes]
zero_count = modulos.count(0)
#if there is at least one 0, i is not a prime
if zero_count > 0:
continue
#if there are no 0, i is a prime, add to the list
else:
primes.append(i)
#return the list of prime numbers
return primes
print(prime_finder(11))`Preformatted text`
def prime_finder(n):
# Write your code here
prime_numbers = []
for i in range(2,n+1):
prime = True
for j in range(2,i):
if i % j == 0:
prime = False
break
if prime:
prime_numbers.append(i)
return prime_numbers
print(prime_finder(11))
This is the first time I do the Prime Number Finder on Python; I have used other languages before.
On the isPrime function, I first identify non-prime number to eliminate; if the number modulo the iteration equals zero but the iteration does not equal the number, it is a good indication that it is not a prime number; the code then breaks; otherwise, it would be a prime number.
def isPrime(n):
for i in range(2,n+1):
if n%i==0 and i!=n:
break
if n%i==0 and i==n:
return True
def prime_finder(n):
newlist = [x for x in range(2,n+1) if isPrime(x) ]
print(newlist)
prime_finder(11)
Hi all,
I completed this challenge (with some youtube assistance on the prime algorithm). I wanted to know if someone could perform a quick code review and provide any recommendations on how this could be improved. Thanks!!
def is_prime(num):
if num == 1 or num == 0:
return False
else:
for i in range(2,num):
if num % i == 0:
return False
break
else:
return True
def prime_finder(n):
listofnums = []
for i in range(n+1):
if is_prime(i) == True:
listofnums.append(i)
return listofnums
print(prime_finder(11))
I completed this challenge by cancelling multiples of 2,3,4,5,6 and 7
I’m sure there must be a more efficient way, nonetheless it worked
def prime_finder(n):
prime_nums = []
for n in range(2,n+1):
if n == 2 or n ==3 or n == 5 or n == 7:
prime_nums.append(n)
if n%2 != 0 and n%3 != 0 and n%4 != 0 and n%5 != 0 and n%6 !=0 and n%7 != 0 and n not in prime_nums:
prime_nums.append(n)
print(prime_nums)
return(prime_nums)
prime_finder(11)
prime_finder(200)
We will never knock invention, ingenuity and initiative, so your less efficient way is cool with us. Your admission of acceptance that there may be a more efficient way is the first step in working toward it. Accept that our code is not perfect is always the best place to start. Kudos.
I would definitely want to take that code back to the drawing board and look for ways to apply the principle of it without all the excessive logic. It can be done, and in all fairness, I’ll leave that to you.
I think one simple solution is to assume that the number is a prime and then test if it isn’t. If that’s the case, remove it from the list. Here is my solution:
def prime_finder(n):
# define empty list to store primes:
out = []
# loop over each number in the range:
for x in range(1, n+1):
# assume it is prime:
out.append(x)
for y in range(2, x):
# if it is not prime, get out of the list
if x % y == 0:
out.pop()
break
# remove 1 because it is not prime
out.remove(1)
return out
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def prime_finder(n):
prime_list = []
# Write your code here
for i in range(1,n+1,1):
if is_prime(i):
prime_list.append(i)
return prime_list
print(prime_finder(39))
Hi there, I just wanted to add a little bit to your solution. I’ve tested it alongside my solution and found out that for 2nd test: prime_finder(200) yours include some numbers that are not actually prime numbers: your solution returned a list of 50 numbers, mine - a list of 46 numbers. Upon closer inspection I realised your solution does not account for the fact that 121, 143, 169, 187 are not prime numbers. That happend because the code hasn’t accounted for multiples of 11, 13, 17 etc. The longer the range, the more chance will be that some multiples haven’t been accounted for.
1 Like
My basic solution
def prime_finder(n):
# Write your code here
primes = []
for number in range(2,n+1):
divisores = 2
for divisor in range(2,number):
if number%divisor == 0:
divisores+=1
if divisores ==2:
primes.append(number)
return primes
print(prime_finder(37))