Couldn't you just set nums equal to 1000 instead of range(1,1000) since you're passing it into a range in the function? (Genuine question, literal n00b here)
@@thefredster55 Nope, because it creates an array of numbers in that given range. So the function iterates through each number in the list and and the filter function creates an object, which then he passes the object through the [list] method which puts all of the values contained in that object into a [list] where the output can be comprehended.
For those concerned for its complexity, remember you can always use sieve of eratosthenes in most cases, this only would be required in case of big numbers
I have been learning python for a while now. And this is the first random short on python i actually understood and would pe capable of replicating. I love this feeling
@@BeasenBear kinda late but he's calling a function called isPrime and you probably didn't define that function (I don't know if it's supposed to be imported or written by yourself, I use C++).
Crazy that when doing a demonstration you focus on ease of understanding the concept rather than efficient of an algorithm unrelated to what he is demonstrating 🤯🤯🤯
Sieve of Eratostenes where you take a vector bool of all trues, then you start a loop from i²(i = 2 to √N) and flag all the multiples in the vector. The position of the trues left in the vector are all the prime numbers till N. This is simpler shorter and well known.
A better is_prime function would be: def is_prime(num): if num == 1 or num == 0: return False for x in range(2, floor(sqrt(num))): if num % n == 0: return False return True This does three things. First, it factors in the fact that 1 is not prime. (It’s neither prime nor composite.) Second, it accounts for the fact that 0 isn’t prime either (as 0 is highly composite, having literally every integer as a factor). And third, it increases the speed of the function since it only needs to go to the square root of the number. This works because every composite number has at least one factor that is greater than 1 and less than or equal to its square root. Indeed, given any integer x such that x > 1, for every factor _a_ of x that is less than √x, there is exactly one other factor _b_ of x that is greater than √x such that _a_ × _b_ = x. (For 1, it has exactly one factor (itself), and its lone factor is also its square root. For 0, it has infinite factors (everything), but its square root (itself) is less than all other whole numbers.) Incidentally, if num is less than 2, then both range(2, num) and range(2, floor(sqrt(num))) will return an empty iterable that will cause the body of the for loop to never be executed. As such, any value for num that is less than 2 will return True for the original version of is_prime, and any value for num that is less than 0, between 0 and 1, or between 1 and 2 will return True for my version of is_prime. We could add a check for nonintegers: if num != floor(num): return False However, that isn’t strictly necessary, since the input should be an integer, and in Python, we assume the developer would not put a fraction into the function. And it’s not like the code would throw an error in such a case, anyways. The better question is with regards to negative numbers. There are four ways to consider this. First, we could just assume that the developer would never input a negative number. This is fine… unless we’re getting input from a user, in which case either the developer or the function should do a check. The second way is to treat all negative numbers as composite on the grounds that they each have at least three factors: 1, itself, and −1 (where we only include −1 as a factor if the number itself is negative), and prime numbers must have exactly 2. In that case, our first conditional would instead be: if num == 1 or num
As a mathematician, #3 and #4 are the correct options here. Either you're working over positive integers, in which case you should throw an exception if negative, or you are working over all integers, which you can use the general definition of a prime element over a commutative ring: p is prime if p is non zero, p is not a unit (here a unit is 1 or -1), and if p=a*b for a and b integers then either p divides a or p divides b. You can see based on this definition that 6 is not a prime: 6=2*3 but 6 does not divide 2 or 3 evenly (i.e. 2/6 and 3/6 are not integers). Similarly for (-6)=(-2)*3, so -6 is not prime. And for positive primes p, we must have p=(±1)*(±p), and p divides ±p. Similarly, -p=(∓1)*(±p), and -p divides ±p. So p is prime is equivalent to saying -p is prime. Notice that over all integers, all primes p have 4 factors: 1, -1, p, -p. It is incorrect to assume all primes have 2 factors, otherwise the only primes over the integers would be 1 and -1.
@@tyrigrut Thank you for your input! I was unaware of how primes work under anything other than nonnegative integers, so I wasn’t aware of the “four factor” definition. I figured there probably _was_ something, though. That said, it is worth noting that, in computing, we don’t always want perfect mathematical accuracy. Sometimes, we prefer speed over accuracy.
@@danielf5393 For long inputs or generators, another generator also outperforms map/filter pipeline. gen = (i for i in list(nums) if is_prime(i)) for x in gen: print(x)
i can do it in one or 2 lines and you can choose the [a,b] : 1- a,b=2,222 2- u = [x for x in list(range(a,b)) if all(x % k != 0 for k in [n for n in list(range(a,b)) if x != n ]) ] 3- print (u)
This is really awesome! I was making a program the other day and I kept getting a similar return to the one you show at the end there and had no idea what was going on! Life saver!
Please use sieve of eratosthenes if you are creating a auxiliary array. Your solution is O(n × √n) which is slower than O(n × log(log(n))) which is sieve of eratosthenes.
@moy92 There are a few ways you can reduce the time complexity because the one in the video is so suboptimal (quadratic time) You can bring it down to O(Nsqrt(N)) by just checking for factors below the square root. But since we are already collecting a list of primes, we can use some kind of sieve algorithm (look up Sieve of Eratosthones on wikipedia). This will be O(NloglogN) or even less depending on the algorithm.
Doesn't this actually run in O(n^2) since for a prime number, he's checking up to n-1 instead of sqrt(n)? Agreed that Sieve of Eratosthenes is the way to go, and it's a really easy algorithm to understand.
Upper limit of sqrt(num) is sufficient when looping, which i find very interesting. Also, you can only loop through the odd numbers if num is not even - which you can check before the loop in is_prime function and return False immediately.
The tradeoff is that a list comprehension is going to store the whole list in memory while filter keeps it as a generator until needed. Both are pythonic and have their uses
For anyone confused, the weird object number thing is called OOP, Objected Oriented Programming, which Python is built from. In order to print something it must be an iterable, and making it a list allows such.
You can save time by checking for divisors till √p , and also . There's no need to jump by 1 , you can check for odd numbers only since even ones aren't primes except 2 . Or better , you jump by 6 and you check for primes bigger than 3 in the form of 6k±1 , since all primes bigger than 3 can be written in the form 6k ± 1
@@alpacalord507 You can build the list as you go; if you let the is_prime function take the existing prime list into account, you can just append new primes you find until you reach the end of the range. However, you can only do this when you’re making the list in order from 2 like this, since you wouldn’t have all the prior primes otherwise
@@thesnakednake And? That's still not solving the problem of checking if a number is prime. You're making a list of primes now, which does not (really) help us checking if a number is prime.
@@alpacalord507 The task in the video is to make a list of the primes from 1 to 1000, not just to check if a number is prime. The function that checks it in this video is a means to an end, not the end goal
During my 1st year at uni, we had this CW in my Data structure & algo class about finding the list of palindromic prime till 100 trillion where time was also a big factor. That CW was pretty interesting tbh.
I would use a generator function to generate a (possibly infinite) sequence of primes by keeping a record of all previously found primes and checking if the next number is divisible by any of those (that should all be smaller than the number) in order. Uses a tiny bit more memory but cuts down on a lot of division operations.
@@plaskut It's possible to make an infinite generator with a sieve but it's actually pretty complicated. The sieve by default marks all multiples of a prime the first time you encounter that prime, which is impossible if the generator is infinite. Instead you'd need to suspend and then resume the markings later as you advance through the generator, which is possible but pretty tricky to get right.
@@OMGclueless I think I might try doing this. I believe it's a divergent function, so at some point it might have to check to see if the universe has ended yet.
You can optimize it more by just checking odd numbers in the range, because even numbers will always be divisible by 2. Or maybe you can just generate odd numbers in a range
@@codeman99-dev timing performance was pretty similar between the two methods. When you check out the disassembled python bytecode (using the dis module), list comprehension has more operations with the python interpreter, so it will most likely not be preferable for code that uses multiple threads (it's more susceptible to global interpreter lock slowing it down)
If you're going to immediately turn it back into a list, don't use filter, use a list comprehension because it's faster. If you only need an iterator, then use filter.
Props to you for making videos where you know that 90% of the comments will be “well actually….” Or some other form of telling you how you are wrong and should have done it their way.
@Harrod Thou Thanks for chiming in. Id say its more ironic you dont view comments like "Thanks for teaching job applicants to not format their code properly and also use a less readable alternative of list comprehensions." as negative. I'm offering support to b001 and props for sticking his neck out there. This field particularly is filled with people who love nothing more than to correct people, not too dissimilar to your response to me. See Stack Overflow for example. Have a good day.
Not sure if it's such a great idea. I personally always report such videos, eg. as "misinformation" and choose for them to not be recommended any more.
You can cut the time down by about 65% if you use the range: range(3, floor(sqrt(num)), 2). You just need to add a case for dividing by 2. This only checks odd numbers, dividing the whole thing by 2, and only going up to the sqrt of that number, which I won't explain here why that is the upper limit. To find how much faster it is, calculate this: (sqrt(2)/2)*0.5, or trust me bc it equals about 0.35, or 65% faster.
@@GordieGii Sieve is going to be significantly faster, but more lines of code. Not sure on the memory usage. But as long as it's clear you are implementing the sieve, difficulty to understand shouldn't be an issue.
@@Rugg-qk4pl That makes sense. The original video said that one objective was to save memory. Since range is an itterable, it only produces the next number and returns it to filter so the list only ever contains the primes. To do Eratosthenes' sieve you need to have all the numbers in the list and then prune them. I suppose you would only need a bool or a bit for each number, but then you would need bit handling routines. Probably already libraries for that sort of thing.
I took a few of the poster's example, as well as @b001 and tweaked the code so it is a function. I have taken a course called python for network engineers, so this may be a novice approach. I have done this program in the past in Pascal and C (yeah I know I old) import math def is_prime(num): if num == 1 or num == 0: return False for n in range(2, int(math.sqrt(num))+1): if num % n == 0: return False return True
for x in range (1,100): num = int(x) test = is_prime(num) if (test): print(num, " is a prime number")
I see it seems something is wrong, in line 5, we need to add if num < 2: return False first, because Python check range(2, num) but in this situation, we check nums ,so Python check range(2,1) then range(2,2)... but range(2,1) is wrong because the original syntax is range(start < end, +1(+1 step)), here range(2 > 1)if Python check it is -1 step but original syntax is +1 step and anymore things can improve but here inconvenient to say there
Great example of what the filter class does, but when converting to other datatypes you should use that specific class's comprehension. Example: print([number for number in range(1000) if is_prime(number)])
Could be more efficient, when checking for a prime you only have to check for factos up too the square root of the number, so if you square root the high end of the range it should work faster!
@@tinahalder8416 in Java you have to specify the type of a variable when declaring it (String, int, char) which cannot be changed afterwards, while in Python the type of a variable is dynamic (i.e. it changes based on the input). This makes it easier to make mistakes if you’re not paying enough attention
@@eazyg885 Python has type hints though. You can get some of the benefits of statically typed languages from having them present. But yeah, lack of proper static typing support, and lack of immutability as an option, are to me the two biggest weaknesses in the language. Third weakness kinda being the dependency management.
Love to see a beginner friendly version of this codeing practice because I know how it looks after generations of programmer optimized the shit out of it in countless different languages since primes are essential for cryptography 😅
Make the range go to the sqrt(num) instead of num, because that is the max you can go without the smallest and largest of the multiples switching. To check is 49 is prime, you only have to check up to 7 because 7*7 = 49 This changes from o(n) to o(sqrt(n)) If you can do this it will save you on at least one coding interview.
@@GoofyGoober6694 ok my bad its hard to tell.. there are just so many people complaining about his method of prime computation when in fact it is about the python language instead of a specific problem you can solve with it
With the Sieve of Eratosthenes, you don't judge each number like that: you create a list of bools you update to eliminate multiples of whatever's still prime. It's more efficient.
This is terribly inefficient lol. You should just Calculate all the prime numbers ahead of time instead of calling this function for every number. Even with that slow function it'd be O(n^2) instead of O(n^3)
Hi mate, I am new to Python. Could you please explain how we can calculate primes ahead of time? Like applying modulo to the list of numbers of a specific range then appending them to a list and printing it? Please correct me if I’m wrong
Good to check the potential factors twice to ensure we can display a nice "Loading..." screen 😊but in case you're looking for efficiency you could start by checking up to sqrt(n), because I'm pretty sure a*b = b*a for integers so if one of the factors is > sqrt(N), the other will for sure have to be below sqrt(N) and we can stop the primality check. I think you'd better show the use of a library rather than careless "tricks"
wow filter function is a time saver, before I used to go for the slower solution : for num in nums: if is_prime(num): print(nums[num]) else: continue ty for the vid🎉
You can massively improve performance of finding primes by searching between 2 and sqrt(n) since if we have two integers x and y such that n = x*y then it’s not possible for both x and y to be greater than the sqrt(n).
You check if it's divisible by every number up to it, but you really only need to check the previous prime numbers, since if it's divisible by a non-prime, it will also be divisible by its prime factorization.
If you ever have to find if a number is prime, you don’t have to divide by every number up until that number. You just have to divide by every number until half of that number. Cuts the amount of calculations by half
The code only provides all odd numbers. Heres a corrected version: nums = range(1, 1000) def is_prime(num): if num < 2: # Handle edge cases return False for x in range(2, int(num**0.5) + 1): # Check divisors up to the square root of num if (num % x) == 0: return False return True primes = list(filter(is_prime, nums)) print(primes)
You can also do: primes = [x for x in nums if is_prime(x) == True] And this will output a list of prime numbers without needing to convert it (if you instantly need to use the list and not the object)
I was about to comment 1 is not prime and you only need to check up to the square root of a number to check if it’s prime. I was happy to see others already said this.
@@philfernandez835 No, only up to the square root (and including it in the case that it happens to be an integer), but square root + 1 is completely unnecessary. The argument is as follows: suppose a number has no prime divisors
Correction: 1 is not prime. My is_prime function is flawed!
You've made a b001 of yourself
just make nums range(2,1000) to exclude 1 instead of making 999 num!=1 comparison
@@damian4601 or just add another condition, because you might want to use 1 in a non prime numbers list
Couldn't you just set nums equal to 1000 instead of range(1,1000) since you're passing it into a range in the function? (Genuine question, literal n00b here)
@@thefredster55 Nope, because it creates an array of numbers in that given range. So the function iterates through each number in the list and and the filter function creates an object, which then he passes the object through the [list] method which puts all of the values contained in that object into a [list] where the output can be comprehended.
Even as a junior web developer, I really like how you do these shorts. It concisely and simply explains whats going on in the shorts.
Thanks so much! Glad you enjoy!
@@b001 keep these shorts coming ❤❤❤❤
His code is horrible. I am sorry but dont watch this guy.
Minor thing, but you can make the prime checking function faster by going up to floor(sqrt(n)) instead.
Could make it even faster by only iterating over odd numbers as well
def is_prime(x):
if x < 2:
return False
if x
@@slammy333 you can make it even faster by only checking n-1 and n+1 where n is each multiple of 6
def isPrime(x):
if x == 1:
return False
if x == 2:
return False
if x == 3:
return True
if x == 4:
return False
This is what you call fast!
Why is a youtube comment thread more productive than my work team... FML
For those concerned for its complexity, remember you can always use sieve of eratosthenes in most cases, this only would be required in case of big numbers
Sieve works for any number, and it is the most optimal way of generating sequences of primes.
Python programmers dont care of the time😅
I have been learning python for a while now. And this is the first random short on python i actually understood and would pe capable of replicating. I love this feeling
primes = [x for x in range(2, 1000) if isPrime(x)]
yeah cuz 1 is not prime
I think his point is to use list comprehension which is the better choice here.
@@BookOfSaints yeah this is list comprehension
It says "isprime" or "Prime" is not defined when I tried this code. What did I miss?
@@BeasenBear kinda late but he's calling a function called isPrime and you probably didn't define that function (I don't know if it's supposed to be imported or written by yourself, I use C++).
scientists: use powerful computers to find new primes
me: types infinity intead of 1000
I tried your code and it worked! I'll check your channel for more!
my man actually made the least efficient function in the history of functions
Not only that, it's also wrong
😂
Crazy that when doing a demonstration you focus on ease of understanding the concept rather than efficient of an algorithm unrelated to what he is demonstrating 🤯🤯🤯
False, I can and do write worse code with more flaws. You're welcome.
im new to python, could you explain why?
Sieve of Eratostenes where you take a vector bool of all trues, then you start a loop from i²(i = 2 to √N) and flag all the multiples in the vector. The position of the trues left in the vector are all the prime numbers till N.
This is simpler shorter and well known.
what you just said has 55 words in it
@ and it took me less than a minute to type. Your point?
(Please dont answer the question is rhetoric.)
@@rohakdebnath8985 im just saying it has 55 words in it
@ ok okay thanks i guess
A better is_prime function would be:
def is_prime(num):
if num == 1 or num == 0:
return False
for x in range(2, floor(sqrt(num))):
if num % n == 0:
return False
return True
This does three things. First, it factors in the fact that 1 is not prime. (It’s neither prime nor composite.) Second, it accounts for the fact that 0 isn’t prime either (as 0 is highly composite, having literally every integer as a factor). And third, it increases the speed of the function since it only needs to go to the square root of the number. This works because every composite number has at least one factor that is greater than 1 and less than or equal to its square root. Indeed, given any integer x such that x > 1, for every factor _a_ of x that is less than √x, there is exactly one other factor _b_ of x that is greater than √x such that _a_ × _b_ = x. (For 1, it has exactly one factor (itself), and its lone factor is also its square root. For 0, it has infinite factors (everything), but its square root (itself) is less than all other whole numbers.)
Incidentally, if num is less than 2, then both range(2, num) and range(2, floor(sqrt(num))) will return an empty iterable that will cause the body of the for loop to never be executed. As such, any value for num that is less than 2 will return True for the original version of is_prime, and any value for num that is less than 0, between 0 and 1, or between 1 and 2 will return True for my version of is_prime. We could add a check for nonintegers:
if num != floor(num):
return False
However, that isn’t strictly necessary, since the input should be an integer, and in Python, we assume the developer would not put a fraction into the function. And it’s not like the code would throw an error in such a case, anyways. The better question is with regards to negative numbers. There are four ways to consider this. First, we could just assume that the developer would never input a negative number. This is fine… unless we’re getting input from a user, in which case either the developer or the function should do a check.
The second way is to treat all negative numbers as composite on the grounds that they each have at least three factors: 1, itself, and −1 (where we only include −1 as a factor if the number itself is negative), and prime numbers must have exactly 2. In that case, our first conditional would instead be:
if num == 1 or num
As a mathematician, #3 and #4 are the correct options here. Either you're working over positive integers, in which case you should throw an exception if negative, or you are working over all integers, which you can use the general definition of a prime element over a commutative ring:
p is prime if p is non zero, p is not a unit (here a unit is 1 or -1), and if p=a*b for a and b integers then either p divides a or p divides b.
You can see based on this definition that 6 is not a prime: 6=2*3 but 6 does not divide 2 or 3 evenly (i.e. 2/6 and 3/6 are not integers). Similarly for (-6)=(-2)*3, so -6 is not prime.
And for positive primes p, we must have p=(±1)*(±p), and p divides ±p. Similarly, -p=(∓1)*(±p), and -p divides ±p.
So p is prime is equivalent to saying -p is prime.
Notice that over all integers, all primes p have 4 factors: 1, -1, p, -p. It is incorrect to assume all primes have 2 factors, otherwise the only primes over the integers would be 1 and -1.
@@tyrigrut
Thank you for your input! I was unaware of how primes work under anything other than nonnegative integers, so I wasn’t aware of the “four factor” definition. I figured there probably _was_ something, though.
That said, it is worth noting that, in computing, we don’t always want perfect mathematical accuracy. Sometimes, we prefer speed over accuracy.
but its almost as if when trying to explain a topic you use the most relative and easy things to understand.
you wrote the whole documentation for this function hats off!
No. There is a better one. Several. This simple sieve is inefficient.
You can also do primes = [i for i in list(nums) if is_prime(i)]
this is the way it should be done
You don’t need to cast to list (and you shouldn’t if nums is a long generator)
@@danielf5393 For long inputs or generators, another generator also outperforms map/filter pipeline.
gen = (i for i in list(nums) if is_prime(i))
for x in gen: print(x)
@@kazzaaz hence prime_generator = ( i for i in nums if is_prime(i) )
I’m complaining about “list(nums)” specifically.
This was the first thing I thought of
Must admit that im a little mad that this didnt show up when i needed it but this tips are very cool and informative
I must admit that I'm a little mad that this didn't show up when I needed it but this tips are very cool and informative!
open book
i can do it in one or 2 lines and you can choose the [a,b] :
1- a,b=2,222
2- u = [x for x in list(range(a,b)) if all(x % k != 0 for k in [n for n in list(range(a,b)) if x != n ]) ]
3- print (u)
For a relatively large number, the isprime func will take a long time to return true or false. Instead of checking every integer
Previous primes upto square root of nums*
@@alexwhitewood6480 yes indeed
This is really awesome! I was making a program the other day and I kept getting a similar return to the one you show at the end there and had no idea what was going on! Life saver!
"all python programers should know this: pep-8" when
💀💀💀
So damn true
What is that?
@@Cristobal512 PEP-8 consists of the Python recommended standards and best practices.
Pep8 is just for jealous and mean programmers..... It just unreadable
Please use sieve of eratosthenes if you are creating a auxiliary array. Your solution is O(n × √n) which is slower than O(n × log(log(n))) which is sieve of eratosthenes.
Okay that time complexity tho
Ikr, it would’ve help to use the root of num but still
newbie here, how would you improve? i thought list comprehensions but dont know ways improve on time complexity
@@moy92 memoization
@moy92 There are a few ways you can reduce the time complexity because the one in the video is so suboptimal (quadratic time)
You can bring it down to O(Nsqrt(N)) by just checking for factors below the square root.
But since we are already collecting a list of primes, we can use some kind of sieve algorithm (look up Sieve of Eratosthones on wikipedia). This will be O(NloglogN) or even less depending on the algorithm.
you don't even need if statements to find prime numbers
getting more and more declarative, love it
Sieve of Eratosthenes is much better for this , but only if u need nums from 1 sieve works with O(n) in spite of this which works withO(n*sqrt(n))
Doesn't this actually run in O(n^2) since for a prime number, he's checking up to n-1 instead of sqrt(n)?
Agreed that Sieve of Eratosthenes is the way to go, and it's a really easy algorithm to understand.
@@vorpal22 yes
In line 5, you can use for x in range(2, num/2). You don't need to check number bigger than the half.
Dude makes me wanna get programing socks and learn python
Upper limit of sqrt(num) is sufficient when looping, which i find very interesting.
Also, you can only loop through the odd numbers if num is not even - which you can check before the loop in is_prime function and return False immediately.
Alternatively, you can use a conditional within a list comprehension: [ n for n in nums if is_prime(n) ]
This is the correct pythonic way of solving it. Avoid using filter whenever possible
Or even : [n for n in nums if n%2==0]
@@e1ke1k96 that’s not how you define a prime number.
The tradeoff is that a list comprehension is going to store the whole list in memory while filter keeps it as a generator until needed. Both are pythonic and have their uses
@@patrickcuster2348 yes, but in the video he used to list function, so a list was the intended output anyway.
from primes import is_prime
print(is_prime(x) for x in range (2, 1000))
primes=[
n
for n in range(2, 1000)
if all(n%x for x in range(2, int(n**0.5)))
]
Yes, but the point of this isn't for is_prime. If you have a complex function, doing the video's way would be a lot more readable
For anyone confused, the weird object number thing is called OOP, Objected Oriented Programming, which Python is built from. In order to print something it must be an iterable, and making it a list allows such.
I love python even more bcoz of you. You are absolutely amazing thanks & keep uploading such clips
He's not teaching you modern Python practices. You should not use filter and map in Python 3.
You can save time by checking for divisors till √p , and also . There's no need to jump by 1 , you can check for odd numbers only since even ones aren't primes except 2 . Or better , you jump by 6 and you check for primes bigger than 3 in the form of 6k±1 , since all primes bigger than 3 can be written in the form 6k ± 1
You only need to check if it's divisible by smaller primes.
But than you need to have a list with primes, so this does not really help
@@alpacalord507 You can build the list as you go; if you let the is_prime function take the existing prime list into account, you can just append new primes you find until you reach the end of the range. However, you can only do this when you’re making the list in order from 2 like this, since you wouldn’t have all the prior primes otherwise
@@thesnakednake And? That's still not solving the problem of checking if a number is prime. You're making a list of primes now, which does not (really) help us checking if a number is prime.
@@alpacalord507 u stupid but your profilpic is meliodas so im not mad
@@alpacalord507 The task in the video is to make a list of the primes from 1 to 1000, not just to check if a number is prime. The function that checks it in this video is a means to an end, not the end goal
During my 1st year at uni, we had this CW in my Data structure & algo class about finding the list of palindromic prime till 100 trillion where time was also a big factor. That CW was pretty interesting tbh.
I would use a generator function to generate a (possibly infinite) sequence of primes by keeping a record of all previously found primes and checking if the next number is divisible by any of those (that should all be smaller than the number) in order. Uses a tiny bit more memory but cuts down on a lot of division operations.
Using a sieve (if you had an upper limit) would be faster than that.
generator with sieve
@@plaskut It's possible to make an infinite generator with a sieve but it's actually pretty complicated. The sieve by default marks all multiples of a prime the first time you encounter that prime, which is impossible if the generator is infinite. Instead you'd need to suspend and then resume the markings later as you advance through the generator, which is possible but pretty tricky to get right.
@@OMGclueless I think I might try doing this. I believe it's a divergent function, so at some point it might have to check to see if the universe has ended yet.
You can optimize it more by just checking odd numbers in the range, because even numbers will always be divisible by 2. Or maybe you can just generate odd numbers in a range
I usually prefer the list comprehension method instead of filter
ie:
[n for n in nums if is_prime(n)]
List comprehension is also faster since. you don't need to convert it back to a list
@@codeman99-dev timing performance was pretty similar between the two methods. When you check out the disassembled python bytecode (using the dis module), list comprehension has more operations with the python interpreter, so it will most likely not be preferable for code that uses multiple threads (it's more susceptible to global interpreter lock slowing it down)
List comprehensions are faster, and in this case, a generator would be even better. Both map and filter are discouraged in Python 3.
If you're going to immediately turn it back into a list, don't use filter, use a list comprehension because it's faster. If you only need an iterator, then use filter.
so if you had a list from 1 to 1000...
*proceeds to show a list from 1 to 999
This also 100% explains why functions are amazing. Return is better than break.
I had to code that in assembly once
Had to code it in brain fuck the other day *cracks knuckles* R/iamverysmart
Dziękujemy.
Thank you!!
I’ve been trying to learn python so this is nice to know I’m still trying to figure something out much out
Thats normal, the basics are the hardest to learn when starting out. After that it gets easier, trust me :)
bro what is that vscode theme its so nice
It's "SynthWave '84" from Robb Owen. It has an option (called "neon dreams") that makes the letters glowy, but i don't use it because i don't like it.
@@hezztiafont?
You should start at 3 and increment by 2 avoiding all even numbers. Saves cpu cycles.
Props to you for making videos where you know that 90% of the comments will be “well actually….” Or some other form of telling you how you are wrong and should have done it their way.
@Harrod Thou Thanks for chiming in. Id say its more ironic you dont view comments like "Thanks for teaching job applicants to not format their code properly and also use a less readable alternative of list comprehensions." as negative. I'm offering support to b001 and props for sticking his neck out there. This field particularly is filled with people who love nothing more than to correct people, not too dissimilar to your response to me. See Stack Overflow for example. Have a good day.
@Harrod Thou the neg comments are there, it just doesn’t take up 90% of the comment section.
Not sure if it's such a great idea. I personally always report such videos, eg. as "misinformation" and choose for them to not be recommended any more.
You can cut the time down by about 65% if you use the range: range(3, floor(sqrt(num)), 2). You just need to add a case for dividing by 2. This only checks odd numbers, dividing the whole thing by 2, and only going up to the sqrt of that number, which I won't explain here why that is the upper limit.
To find how much faster it is, calculate this: (sqrt(2)/2)*0.5, or trust me bc it equals about 0.35, or 65% faster.
Nice demo of filter(). In reality one should use the Eratosthenes' sieve to obtain large lists of primes in python
In double reality one should download a large list of primes
Is that because it takes less time, less ram, fewer lines of code, or is easier to understand?
@@GordieGii Sieve is going to be significantly faster, but more lines of code. Not sure on the memory usage. But as long as it's clear you are implementing the sieve, difficulty to understand shouldn't be an issue.
@@Rugg-qk4pl That makes sense. The original video said that one objective was to save memory. Since range is an itterable, it only produces the next number and returns it to filter so the list only ever contains the primes. To do Eratosthenes' sieve you need to have all the numbers in the list and then prune them. I suppose you would only need a bool or a bit for each number, but then you would need bit handling routines. Probably already libraries for that sort of thing.
I took a few of the poster's example, as well as @b001 and tweaked the code so it is a function. I have taken a course called python for network engineers, so this may be a novice approach. I have done this program in the past in Pascal and C (yeah I know I old)
import math
def is_prime(num):
if num == 1 or num == 0:
return False
for n in range(2, int(math.sqrt(num))+1):
if num % n == 0:
return False
return True
for x in range (1,100):
num = int(x)
test = is_prime(num)
if (test):
print(num, " is a prime number")
Beautiful exponential time complexity
It's quadratic, not exponential
@@lawnjittle good catch. you're right
I see it seems something is wrong, in line 5, we need to add if num < 2: return False first, because Python check range(2, num) but in this situation, we check nums ,so Python check range(2,1) then range(2,2)... but range(2,1) is wrong because the original syntax is range(start < end, +1(+1 step)), here range(2 > 1)if Python check it is -1 step but original syntax is +1 step and anymore things can improve but here inconvenient to say there
Great example of what the filter class does, but when converting to other datatypes you should use that specific class's comprehension. Example: print([number for number in range(1000) if is_prime(number)])
Thank you. I love your channel
Sheesh nice trick my friend!!
you can use the millertest to find prime numbers more efficiently
Just use Sieve of Eratosthenes, get better time complexity of O(nloglogn)
That’s the way I’d do it. Much better than this method, sad your only upvote is me.
The prime thing was just an example to show off the filter function
Combine that with memorization, you can reduce the big O
@@jackomeme I'm late, but how? I can't really see it
I'm just learning python, thanks for showing me the filter function!
we have all of the prime numbers
1, 2, 3 💀💀
It’s prime, what’s wrong?
@@-sn4k3-94 1 isn’t a prime number tho
@@finnyass1407argument of semantics, it's generally not considered a prime but the arguments are vibes
For increased readability, you should prefer a list comprehension instead of the filter method
primes = [x for x in nums if is_prime(x)]
I want to learn to code but it’s intimidating tbh . I’m no genius .
Not gonna let that stop me from going for it though 💯
less gooo
it has a steep learning curve in the beginning but gets very easy, like learning to drive a car
Prefect and easy to follow
People using pandas: 😂🤣
You can also remove checks by going up to the square root of the value because anything past that would a repeat of something already checked.
Could be more efficient, when checking for a prime you only have to check for factos up too the square root of the number, so if you square root the high end of the range it should work faster!
personally I'd use a list comprehension myself
primes = [num for num in range(0,1000) if is_prime(num)]
print(primes)
Print(list(filter(list(map(lambda x: x is not any([x%y==0 for y un range (2,x)]), [i for i in range (1000)])))))
Imao😮
Bro, You are truly pythonic. :)
Imagine changing x%y==0 to (not x%y) tho
Thanks man you're the best!
Thanks for teaching job applicants to not format their code properly and also use a less readable alternative of list comprehensions.
beat me to it
Was looking for the list comprehension answer :-D
Actually terrible way to write python. Do you think its just bait? I would not merge that
Bro you guys unironically code in python it doesn't matter anyways
What should we use sensei?
If you need a list of primes up to x, using a sieve function might be more performant
Please don’t stop making shorts, your shorts content is the best I have seen 🙌🏽
Then you have seen nothing
Proceeds to create the riemen hypothesis*
Using list comprehension for this would be more pythonic
I hate list comphrensions
@@wintur2856seems like changing programming language is the best option for you.
Another fucking thing to memorize thank you
Pythons freedom to not declare variables and data types makes me appreciate Java.
Huuhhh? Ur word confuses me wise man
@@tinahalder8416 in Java you have to specify the type of a variable when declaring it (String, int, char) which cannot be changed afterwards, while in Python the type of a variable is dynamic (i.e. it changes based on the input). This makes it easier to make mistakes if you’re not paying enough attention
@@eazyg885 Python has type hints though. You can get some of the benefits of statically typed languages from having them present.
But yeah, lack of proper static typing support, and lack of immutability as an option, are to me the two biggest weaknesses in the language. Third weakness kinda being the dependency management.
Love to see a beginner friendly version of this codeing practice because I know how it looks after generations of programmer optimized the shit out of it in countless different languages since primes are essential for cryptography 😅
If you wanna use filter, go back to JavaScript! Pythonic would be, to use a list comprehension.
Make the range go to the sqrt(num) instead of num, because that is the max you can go without the smallest and largest of the multiples switching.
To check is 49 is prime, you only have to check up to 7 because 7*7 = 49
This changes from o(n) to o(sqrt(n))
If you can do this it will save you on at least one coding interview.
🤓*snorts* actually, you should have set the range to 1,1001 to print out the entire 1000 numbers instead of 999
@@MCRuCr it's ironic
@@GoofyGoober6694 ok my bad its hard to tell.. there are just so many people complaining about his method of prime computation when in fact it is about the python language instead of a specific problem you can solve with it
With the Sieve of Eratosthenes, you don't judge each number like that: you create a list of bools you update to eliminate multiples of whatever's still prime. It's more efficient.
This is terribly inefficient lol. You should just Calculate all the prime numbers ahead of time instead of calling this function for every number.
Even with that slow function it'd be O(n^2) instead of O(n^3)
Thanks for the feedback! You're totally right, but the main point of the video was to show what the filter function does.
@@b001 fair enough
Hi mate, I am new to Python. Could you please explain how we can calculate primes ahead of time? Like applying modulo to the list of numbers of a specific range then appending them to a list and printing it? Please correct me if I’m wrong
Good to check the potential factors twice to ensure we can display a nice "Loading..." screen 😊but in case you're looking for efficiency you could start by checking up to sqrt(n), because I'm pretty sure a*b = b*a for integers so if one of the factors is > sqrt(N), the other will for sure have to be below sqrt(N) and we can stop the primality check. I think you'd better show the use of a library rather than careless "tricks"
wow filter function is a time saver, before I used to go for the slower solution :
for num in nums:
if is_prime(num):
print(nums[num])
else:
continue
ty for the vid🎉
You can shorten the function if the range is num//2+1
```
from math import floor, sqrt
def is_prime(x):
if x==1:
return False
for i in range(floor(sqrt(x)):
if x%i == 0:
return False
return True
```
The range should be range(2, floor(sqrt(x))+1) tho
Alternative way that is much easier to remember: condition list comprehension
You can massively improve performance of finding primes by searching between 2 and sqrt(n) since if we have two integers x and y such that n = x*y then it’s not possible for both x and y to be greater than the sqrt(n).
if you want primes in a certain range it is faster to use the Sieve of Eratosthenes (look it up) it is actually really easy
nums=range (1,1000)
def is_prime(num):
for × range(2,num):
if(num%×) == 0:
return False
return True
primes=list(filter(is_prime,nums))
print (primes)
Wow, that one was very helpful
You could also use primes = [x for x in nums if is_prime(x)]
I love it, i have no idea whats going on but i love it ❤😂
You check if it's divisible by every number up to it, but you really only need to check the previous prime numbers, since if it's divisible by a non-prime, it will also be divisible by its prime factorization.
If you ever have to find if a number is prime, you don’t have to divide by every number up until that number. You just have to divide by every number until half of that number. Cuts the amount of calculations by half
This is really nice, but you can't save shorts to your playlists so you'd have a library of useful tips and methods.
thanks for the tips!
The code only provides all odd numbers. Heres a corrected version:
nums = range(1, 1000)
def is_prime(num):
if num < 2: # Handle edge cases
return False
for x in range(2, int(num**0.5) + 1): # Check divisors up to the square root of num
if (num % x) == 0:
return False
return True
primes = list(filter(is_prime, nums))
print(primes)
This is a problem I was literally working on today. I saw a really similar solution on stack overflow
A quicker way is to check if a number 'n' satisfies the equation n = 6*m + 1, where 'm' is a positive natural number.
That won't work because it doesn't guarantee that the number is prime. Not all 6m+1 are prime numbers.
You can also do:
primes = [x for x in nums if is_prime(x) == True]
And this will output a list of prime numbers without needing to convert it (if you instantly need to use the list and not the object)
You don’t need the == True
@@gavinhofer4588 you're right! my bad
Thanks for helping
I was about to comment 1 is not prime and you only need to check up to the square root of a number to check if it’s prime. I was happy to see others already said this.
square root + 1 right?
@@philfernandez835 No, only up to the square root (and including it in the case that it happens to be an integer), but square root + 1 is completely unnecessary. The argument is as follows: suppose a number has no prime divisors