Wow, I spent so long trying to get my head around an algorithm to solve this in order to create a flowchart. Gave myself a headache. Didn't get it. Less that 3min into your video I could suddenly see the light, lol. Cheers xx
Awesome approach! I was originally trying to find all prime numbers under 2,000,000 and found that it was extremely inefficient (I never met the end of the code). I did n/2 instead of n**.5. I saw this video and loved your approach to the problem on how to get the best possible solution instead of just throwing things at your viewers.
Hi Prof. James, Fantastic vid! I learned valuable information watching that. Thank you!I also noticed that the same result can be achieved without doing Boolean comparison. I removed all isPrime lines and replaced the if isPrime line with else:, and it works just fine. It saves me 1 less total line in the code.But regardless, thank you very much! I gained deeper understanding about nested for loops from this vid. I also learned a little bit on timing optimization.
Thanks, My algorithm takes too much time, and specially taking the sq.root of the number part, I've seen it in many times but didn't understand the reason behind it, this helped me a lot.
Thank you very much Joe for this share. I really have learned something very interesting in the algorithmic field. Please don't get me wrong, but I would like to improve the performance of this algorithm a little bit more. I think that the expression «int(x**0.5)+1» into 2nd for cycle slows down the script if you may be searching for a really big number of primes, because in each iteration, the processor has to read the variable «x», calculate its square root, add 1 and only then, make the compare expression with «y» variable. This consumes many processor cycles. However, if you do this math into a new variable just before the 2nd for cycle begins, lets say: rSide = int(x**0.5)+1 for y in range(2, rSide): ... It really would speed up the algorithm, because it will only be needed, at each «y» iteration, the time for reading the variable «rSide» and compare it with the «y» value. I hope that this make sense for everyone. Best regards. (Sorry if the upper syntax may be wrong in Python, but I usually don't program in Python, hopefully everyone may understand and make the right changes for the right syntax.)
Another useful trick for this is wrapping those two loops in an if statement which will check a single thing: if the number is even) Any even number greater than 2 is not prime. Then, if it's odd, all the calculations from the tutorial happen.
Olie, that's pretty easy. you just change the if statement at the end to : if isPrime: primeList.append(x) primeList.append(", prime.") else primeList.append(x) primeList.append(", not prime")
Building an array, 2 to n, setting every multiple of numbers which aren't already 0 up to the square root of n to 0 and printing everything which isn't zero would give a much faster algorythm than anything x % y could achieve, it'll just take some RAM. With your setting, if you'd make 2 and 3 an exception and just checking every 6th number +/- 1 would result in even less numbers to proof. Another way is each prime which isn't 2 or 3: prime² - 1 % 24 = 0
Good one. Could speed it up a little more by checking only odds after 2, using range(3, n+1, 2) for both for loops (n is max or sqrt expression). Preload primeList with 2 for completeness.
It's not just the odds. I've previously been working with the formula 6*n+-1 which gives you potential primes given n is a positive integer. This means you cut the numbers down to 2/3 of the odds.
You may not wish to use the keyword "max" as a variable name and only do the square root operation once. The following Python code, using a binary array and list comprehension, should perform better. Just a suggestion. ------------------------------------------------------------------------------------------------ max1 = int(input("Find primes up to what number? :")) max2 = int(max1 ** 0.5) + 1 barray = (max1 + 1)*[True] index = 2 while index
+New to Code you have the right idea using a while loop instead of the for loop, but you have to make a few other changes. BTW, your statement should be while len(primeList) < 1000, so you don't put
Thanks for the video professor. It was very helpful. But I am stuck at a question in this video. Why are we using 'if isPrime' before the print statement and the append statement? Also when I remove the 'if isPrime' ,before the print as well as append statements, then there are repeated list of prime numbers in the console after running the module. Can you please explain why is it happening and what role and importance of the 'is isPrime' statement before these statements? Thanks
+Begin ner the program uses a boolean variable called isPrime to know whether each number is prime or not. Each time through the outer loop you get a new number, let's say 25. We start by assuming 25 is Prime, (ie. we set isPrime to True). Then we use the inner loop to see if we can find a number that divides evenly into 25. If we find one then we set isPrime for 25 to False. So when we exit the inner loop we only want to print the numbers that still have this isPrime flag set to True. Our check "if isPrime" is equivalent to "if isPrime == True", both those two statements do exactly the same thing. Two things that may confuse you: the use of a boolean flag in a loop. This is a very common technique in computer programming. and our if statement not needing the ==. That's because the IF statement needs a boolean value (True or False). But you don't necessarily need to do a comparison to get that boolean value. You could say "if True", then the if statement would always execute.
and what happens when I do not use the "if isPrime" before appending x in the list? Why does all prime numbers start repeating themselves when asked to print?
+Begin ner I don't understand why you would take that if statement out. I don't know what the program will do if you made changes to it that I can't see. My guess is that you have the print statement indented too far. If you post code I can comment on it.
I have made the same programme and not added True or False, that affects a lot. Please can you explain why you added True false I can't able to understand that. BTW, you are the greatest.
If you start with 2 and explain the complete process, it would be helpful. How do you explain it? if 2 % y == 0 for y = 2 (Refer run time video : 2:31) Is not 2 evenly divided by 2 here? by your statement, it is not a prime. Right? Or is there any other logic here.
... yes, and 29 % 29 = 0; yet 29 is prime. In fact, y % y = 0 for all y ≥ 1, so you need to test for divisors of x, that are no greater than x-1. And you can see that at 2:31, he tests 9 for divisors that go from 2 through 8, stopping 1 short of 9.
I found another way to optimize it. Instead of checking every single number, you can check only the odd numbers. In this case: for x in range(3, 10000, 2): isPrime = True for y in range(2, int(potential_prime**0.5)+1): if potential_prime % div == 0: isPrime = False break if isPrime: primeList.append(x) print(primeList Any thoughts?
Why skip just the even numbers after 2? After finding a prime number, why not skip all of its multiples? Why not eliminate most arithmetic operations? Why not just do the square root once? What is the optimal solution? (See my suggested code for answers.)
x**0.5 = x^½, and the one-half power of x is the square root of x. This follows from properties of exponents. Recall that xᵐ·xⁿ = xᵐ⁺ⁿ Apply this rule with m = n = ½, and you get: (x^½)(x^½) = x^(½+½) = x¹ = x But (x^½)(x^½) = (x^½)² So (x^½)² = x x^½ = √x As for adding +1, Joe explains that in the video; range(min, max) goes up to, but *not including* max. So in order to include max itself, you need: range(min, max+1).
Why do we set a isPrime boolean to True at the beginning? Completely new to programming so would like all things that probably seem 'obvious' spelt out to me in the most simple way possible please. Can anyone help?
We start by assuming x is prime (isPrime = True), then we test every number below x to see if it divides evenly. If we find a factor that divides evenly then we know x is not prime. If we finish the loop without finding an even factor then isPrime will still be True. In logic, this is called proof by contradiction.
Correction: 1 is not prime. This is because of the definition of prime, which excludes 1. 1 is neither prime nor composite; it is a *unit* among the integers.
This can be done even faster! Much much faster! It is not necesary to divide to all numbers [2,3,4,5,6,7..], just use the primes you saved until now [2,3,5,7,11,...]. This is because if a number is not divisible by 2, it is not divisible by all the rest even numbers [4,6,8,...]. So, if you tested 2, do not try with 4 because you are loosing time. On the same way, if you tested 3, do not try with [6,9,12,15,18....], and so on. With this idea, the code could be: max = int(input('Find primes up to what number? : ')) prime_list=[2] for x in range(3, max+1, 2): is_prime = True stop = x**0.5 for y in prime_list: # stop: break if x % y == 0: is_prime = False break if is_prime: prime_list.append(x) print(prime_list) # Regards.
We start by setting it to true, then do a series of tests. If we find one case where it’s not true then we change it to false. Think of it as a flag or an alarm light on a dashboard.
Joe James, I would really recommend PyCharm Community Edition. It's got auto-completion which I like a lot, and does indentation for you, plus suggested edits to fix errors, like importing certain modules.
I find the below code efficient(written by me). Can it be improved in any way?...Any help is greatly appreciated a=[2,3] n=int(input('Enter limit:')) for i in range(5,n,2): #not checking primeness in even numbers flag=True for j in a: #applying mod only by a prime number if(i%j==0): #(composite numbers smaller than i are already divisible by numbers in list a) flag=False break if(flag): a.append(i) print(a) edit: Of course using ur ideas.Great video edit 2:added my comments.
I missed a trap which i realized(limit to sq. root) later a=[2,3] n=int(input('Enter limit:')) for i in range(5,n,2): #not checking primeness in even numbers flag=True k=int(i**.5)+1 for j in a: #applying mod only by a prime number if(i%j==0 and j
Thanks for the example. I tried to use that and I think I have the indents all wrong. This is what I have: app3.vocusgr.com/ViewAttachment.aspx?EID=vZR5Y4hXkVWu946S007TjFMGHODpqU6WQ6y%2f7WKEsdY%3d I am not sure if the second "while" is considered a nested loop inside the first while. Can you take a look at the code and let me know what you think I am doing wrong. Thanks in advance!
Why wont this work for me? primeList =[] compositeList = [] max= int(input("Find prime number up to what number? : ")) for x in range (2, max+1): isPrime=True for y in range (2,x): if x % y == 0: isPrime =False if isPrime: primeList.append(x) else: compositeList(x)
+NSkiiez Nice job. your last line should be compositeList.append(x) also, I got some weird error with the else statement, so I had to delete and retype the whole line. There must be some invisible character encoding problem with that line that.
+Olie to answer your question, I think Joe didn't get it quite right. You should have if isPrime: primeList.append('%d prime'%x) else: primeList.append('%d not prime'%x) Joe's answer puts the number and the string as separate elements which is not what you want. Btw one is NOT prime, please try to not make this common mistake.
this helped me a lot of understanding the prime number algorithm and the complexity of the program.Thank you
Wow, I spent so long trying to get my head around an algorithm to solve this in order to create a flowchart. Gave myself a headache. Didn't get it. Less that 3min into your video I could suddenly see the light, lol. Cheers xx
This is God-sent.
Thanks a million. You just saved my life
Awesome approach! I was originally trying to find all prime numbers under 2,000,000 and found that it was extremely inefficient (I never met the end of the code). I did n/2 instead of n**.5. I saw this video and loved your approach to the problem on how to get the best possible solution instead of just throwing things at your viewers.
Thanks
Hi Prof. James, Fantastic vid! I learned valuable information watching that. Thank you!I also noticed that the same result can be achieved without doing Boolean comparison. I removed all isPrime lines and replaced the if isPrime line with else:, and it works just fine. It saves me 1 less total line in the code.But regardless, thank you very much! I gained deeper understanding about nested for loops from this vid. I also learned a little bit on timing optimization.
thank you so much, the explaining was in very simple way that anyone could understand
Thanks, My algorithm takes too much time, and specially taking the sq.root of the number part, I've seen it in many times but didn't understand the reason behind it, this helped me a lot.
that was dope man!
Really appreciate it, thank you!
The explanation about why only going up to the square of the number was nice. :)
helpped real quick, left a like btw
Ok I got it. Thank for all your help!
Thank you so much for this lecture. This is best explanation I found on TH-cam ever about this concept.
That's so helpful! Thank you for posting that!!
this helped me w my test, thanks
Thank you very much Joe for this share.
I really have learned something very interesting in the algorithmic field. Please don't get me wrong, but I would like to improve the performance of this algorithm a little bit more.
I think that the expression «int(x**0.5)+1» into 2nd for cycle slows down the script if you may be searching for a really big number of primes, because in each iteration, the processor has to read the variable «x», calculate its square root, add 1 and only then, make the compare expression with «y» variable. This consumes many processor cycles. However, if you do this math into a new variable just before the 2nd for cycle begins, lets say:
rSide = int(x**0.5)+1
for y in range(2, rSide):
...
It really would speed up the algorithm, because it will only be needed, at each «y» iteration, the time for reading the variable «rSide» and compare it with the «y» value. I hope that this make sense for everyone.
Best regards.
(Sorry if the upper syntax may be wrong in Python, but I usually don't program in Python, hopefully everyone may understand and make the right changes for the right syntax.)
Yes, great point
@@oggiai Thank you. :-)
Thank you! Really helpful
Another useful trick for this is wrapping those two loops in an if statement which will check a single thing: if the number is even) Any even number greater than 2 is not prime. Then, if it's odd, all the calculations from the tutorial happen.
Thanks for the performance comparisons. :)
That's awesome!!
Olie, that's pretty easy. you just change the if statement at the end to :
if isPrime:
primeList.append(x)
primeList.append(", prime.")
else
primeList.append(x)
primeList.append(", not prime")
I am liking this guy. Imagine he is your programming teacher in your school. Dream
Thanks. 😃
Building an array, 2 to n, setting every multiple of numbers which aren't already 0 up to the square root of n to 0 and printing everything which isn't zero would give a much faster algorythm than anything x % y could achieve, it'll just take some RAM.
With your setting, if you'd make 2 and 3 an exception and just checking every 6th number +/- 1 would result in even less numbers to proof.
Another way is each prime which isn't 2 or 3: prime² - 1 % 24 = 0
Nice solution. 😃
Good one. Could speed it up a little more by checking only odds after 2, using range(3, n+1, 2) for both for loops (n is max or sqrt expression). Preload primeList with 2 for completeness.
Yes, great inputs. Thanks Kirby. I will probably revise my code on GitHub when I get time.
It's not just the odds. I've previously been working with the formula 6*n+-1 which gives you potential primes given n is a positive integer. This means you cut the numbers down to 2/3 of the odds.
Check with only prime numbers before square root of x (use prime list with in the code)
Hey man, are you using IDLE or Note++?
explanation is very nice thanks a lot
You may not wish to use the keyword "max" as a variable name and only do the square root operation once.
The following Python code, using a binary array and list comprehension, should perform better. Just a suggestion.
------------------------------------------------------------------------------------------------
max1 = int(input("Find primes up to what number? :"))
max2 = int(max1 ** 0.5) + 1
barray = (max1 + 1)*[True]
index = 2
while index
Nice code, but conceptually a bit more complicated to explain.
@@oggiai There are times when one must take that mental leap and visualize the binary solution to a problem--no ifs, no breaks, no modulos.
Is sieve Erathosthenes best solution for that
It is based on elimination and has linear space complexity
Joe, if I only needed to find the first 1000 prime numbers, how should I do that? I tried using while len(primeList
+New to Code you have the right idea using a while loop instead of the for loop, but you have to make a few other changes. BTW, your statement should be while len(primeList) < 1000, so you don't put
How would you alter the code to find all the prime factor of the users input?
That outtro music hits different after the coding revelations Joe lays on you.
Thank you sir
Thanks for the video professor. It was very helpful. But I am stuck at a question in this video.
Why are we using 'if isPrime' before the print statement and the append statement?
Also when I remove the 'if isPrime' ,before the print as well as append statements, then there are repeated list of prime numbers in the console after running the module.
Can you please explain why is it happening and what role and importance of the 'is isPrime' statement before these statements?
Thanks
+Begin ner the program uses a boolean variable called isPrime to know whether each number is prime or not. Each time through the outer loop you get a new number, let's say 25. We start by assuming 25 is Prime, (ie. we set isPrime to True). Then we use the inner loop to see if we can find a number that divides evenly into 25. If we find one then we set isPrime for 25 to False. So when we exit the inner loop we only want to print the numbers that still have this isPrime flag set to True. Our check "if isPrime" is equivalent to "if isPrime == True", both those two statements do exactly the same thing.
Two things that may confuse you: the use of a boolean flag in a loop. This is a very common technique in computer programming. and our if statement not needing the ==. That's because the IF statement needs a boolean value (True or False). But you don't necessarily need to do a comparison to get that boolean value. You could say "if True", then the if statement would always execute.
+Begin ner I also have a video on Python IF statements here that might help you,
th-cam.com/video/L6WH8A23Eqg/w-d-xo.html
and what happens when I do not use the "if isPrime" before appending x in the list? Why does all prime numbers start repeating themselves when asked to print?
+Begin ner I don't understand why you would take that if statement out. I don't know what the program will do if you made changes to it that I can't see. My guess is that you have the print statement indented too far. If you post code I can comment on it.
Parabéns , obrigado...
I have made the same programme and not added True or False, that affects a lot.
Please can you explain why you added True false I can't able to understand that.
BTW, you are the greatest.
Are you running python 3.1?
If you start with 2 and explain the complete process, it would be helpful. How do you explain it?
if 2 % y == 0 for y = 2 (Refer run time video : 2:31) Is not 2 evenly divided by 2 here?
by your statement, it is not a prime. Right? Or is there any other logic here.
... yes, and
29 % 29 = 0; yet 29 is prime.
In fact,
y % y = 0
for all y ≥ 1, so you need to test for divisors of x, that are no greater than x-1.
And you can see that at 2:31, he tests 9 for divisors that go from 2 through 8, stopping 1 short of 9.
I found another way to optimize it. Instead of checking every single number, you can check only the odd numbers. In this case:
for x in range(3, 10000, 2):
isPrime = True
for y in range(2, int(potential_prime**0.5)+1):
if potential_prime % div == 0:
isPrime = False
break
if isPrime:
primeList.append(x)
print(primeList
Any thoughts?
Why skip just the even numbers after 2? After finding a prime number, why not skip all of its multiples? Why not eliminate most arithmetic operations? Why not just do the square root once? What is the optimal solution? (See my suggested code for answers.)
can you explain on how x**0.5 is sqrt of x and why are we adding + 1 to it? I am not able to grasp that particular part
x**0.5 = x^½, and the one-half power of x is the square root of x.
This follows from properties of exponents. Recall that
xᵐ·xⁿ = xᵐ⁺ⁿ
Apply this rule with m = n = ½, and you get:
(x^½)(x^½) = x^(½+½) = x¹ = x
But
(x^½)(x^½) = (x^½)²
So
(x^½)² = x
x^½ = √x
As for adding +1, Joe explains that in the video; range(min, max) goes up to, but *not including* max.
So in order to include max itself, you need:
range(min, max+1).
what is the last line(s) of code at 12:46? I can see the print(primeList) has more to it, but i can't see it.
rdrumm729 no, that's it. there's nothing after that.
You can see the full code on Github here, github.com/joeyajames/Python
Thank you
Why do we set a isPrime boolean to True at the beginning? Completely new to programming so would like all things that probably seem 'obvious' spelt out to me in the most simple way possible please. Can anyone help?
We start by assuming x is prime (isPrime = True), then we test every number below x to see if it divides evenly. If we find a factor that divides evenly then we know x is not prime. If we finish the loop without finding an even factor then isPrime will still be True. In logic, this is called proof by contradiction.
how would you alter the code so that it would state whether each number prime or not, e.g 1 prime , 2 prime ,3 prime , 4 not prime
Correction: 1 is not prime.
This is because of the definition of prime, which excludes 1.
1 is neither prime nor composite; it is a *unit* among the integers.
This can be done even faster! Much much faster! It is not necesary to divide to all numbers [2,3,4,5,6,7..], just use the primes you saved until now [2,3,5,7,11,...]. This is because if a number is not divisible by 2, it is not divisible by all the rest even numbers [4,6,8,...]. So, if you tested 2, do not try with 4 because you are loosing time. On the same way, if you tested 3, do not try with [6,9,12,15,18....], and so on. With this idea, the code could be:
max = int(input('Find primes up to what number? : '))
prime_list=[2]
for x in range(3, max+1, 2):
is_prime = True
stop = x**0.5
for y in prime_list: # stop:
break
if x % y == 0:
is_prime = False
break
if is_prime:
prime_list.append(x)
print(prime_list)
# Regards.
Could you please explaim IsPrime. I know it is a Boolean type but how does it help in this case. I am new to coding.
We start by setting it to true, then do a series of tests. If we find one case where it’s not true then we change it to false. Think of it as a flag or an alarm light on a dashboard.
i want to count the output
I use Notepad++
Joe James, I would really recommend PyCharm Community Edition. It's got auto-completion which I like a lot, and does indentation for you, plus suggested edits to fix errors, like importing certain modules.
why did you add +1
nice effort, but it wont work for the number 2
I find the below code efficient(written by me). Can it be improved in any way?...Any help is greatly appreciated
a=[2,3]
n=int(input('Enter limit:'))
for i in range(5,n,2): #not checking primeness in even numbers
flag=True
for j in a: #applying mod only by a prime number
if(i%j==0): #(composite numbers smaller than i are already divisible by numbers in list a)
flag=False
break
if(flag):
a.append(i)
print(a)
edit: Of course using ur ideas.Great video
edit 2:added my comments.
Looks great. I don't think there's much else you can do to optimize it.
I missed a trap which i realized(limit to sq. root) later
a=[2,3]
n=int(input('Enter limit:'))
for i in range(5,n,2): #not checking primeness in even numbers
flag=True
k=int(i**.5)+1
for j in a: #applying mod only by a prime number
if(i%j==0 and j
does this work on python 3.1?
It should work in all Python 3.x versions. I'm running ver 3.3.2 now.
Seems easy den c,c++ and java
Thanks for the example. I tried to use that and I think I have the indents all wrong. This is what I have: app3.vocusgr.com/ViewAttachment.aspx?EID=vZR5Y4hXkVWu946S007TjFMGHODpqU6WQ6y%2f7WKEsdY%3d
I am not sure if the second "while" is considered a nested loop inside the first while. Can you take a look at the code and let me know what you think I am doing wrong. Thanks in advance!
+New to Code yes, your indentation is wrong on the last 4 lines before the print. compare to mine here, github.com/joeyajames/Python
Then how to count it
len(primeList) gives the length of the array i.e. the number of primes
Why wont this work for me?
primeList =[]
compositeList = []
max= int(input("Find prime number up to what number? : "))
for x in range (2, max+1):
isPrime=True
for y in range (2,x):
if x % y == 0:
isPrime =False
if isPrime:
primeList.append(x)
else:
compositeList(x)
+NSkiiez Nice job. your last line should be compositeList.append(x)
also, I got some weird error with the else statement, so I had to delete and retype the whole line. There must be some invisible character encoding problem with that line that.
+Joe James I keep getting "IOError: The handle is invalid" with the max= int(input("Find prime number up to what number? : "))
+NSkiiez I didn't have that problem. Try commenting out everything else and see if that line alone will run. What version Python are you using?
Im using Processing 3. version 3.0.1
+Olie to answer your question, I think Joe didn't get it quite right. You should have
if isPrime: primeList.append('%d prime'%x)
else: primeList.append('%d not prime'%x)
Joe's answer puts the number and the string as separate elements which is not what you want. Btw one is NOT prime, please try to not make this common mistake.
I do not get this i am sooo sorry joe
any1 else tpnig wif lef hand?