Generating Python yield for Prime number [duplicate]
up vote
2
down vote
favorite
This question already has an answer here:
Fastest way to list all primes below N
30 answers
Simple Prime Generator in Python
22 answers
I created a sample code in python with yield.
I am trying to fine tune this code below to be a bit more efficient in execution time.
def gen_prime():
a =
i = 2
j = 1
m = 0
while True:
if i == 2:
a.append(i)
yield i
m = 0
for j,k in enumerate(a):
if i % a[j] == 0 and i not in a:
m = 0
break
if i % a[j] != 0:
m += 1
if m >= 1:
a.append(i)
yield i
i += 1
Could you please share some pointers with me to make the code run faster.
python generator primes yield execution-time
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
asked Nov 10 at 15:56
Pandora-Box
183
marked as duplicate by Daniel Mesejo, jonrsharpe, Austin Hastings, Håken Lid, James K Polk Nov 11 at 2:34
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
up vote
2
down vote
favorite
This question already has an answer here:
Fastest way to list all primes below N
30 answers
Simple Prime Generator in Python
22 answers
I created a sample code in python with yield.
I am trying to fine tune this code below to be a bit more efficient in execution time.
def gen_prime():
a =
i = 2
j = 1
m = 0
while True:
if i == 2:
a.append(i)
yield i
m = 0
for j,k in enumerate(a):
if i % a[j] == 0 and i not in a:
m = 0
break
if i % a[j] != 0:
m += 1
if m >= 1:
a.append(i)
yield i
i += 1
Could you please share some pointers with me to make the code run faster.
python generator primes yield execution-time
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
asked Nov 10 at 15:56
Pandora-Box
183
marked as duplicate by Daniel Mesejo, jonrsharpe, Austin Hastings, Håken Lid, James K Polk Nov 11 at 2:34
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
Because you are looking for improvements to working code, I'll suggest that you might want to submit this to Code Review instead.
– Austin Hastings
Nov 10 at 16:01
If you moveyield 2before the loop and start ati = 3, you can remove thei not in acheck. Also, no need to useenumerate; just usekinstead ofa[j]. You don’t need to checkif i % a[j] != 0. Using actual names likeprimesinstead of single letters likeawill help with readability.
– Ry-♦
Nov 10 at 16:02
stop the enumeration at the sqrt of i.
– Will Ness
Nov 10 at 18:24
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
This question already has an answer here:
Fastest way to list all primes below N
30 answers
Simple Prime Generator in Python
22 answers
I created a sample code in python with yield.
I am trying to fine tune this code below to be a bit more efficient in execution time.
def gen_prime():
a =
i = 2
j = 1
m = 0
while True:
if i == 2:
a.append(i)
yield i
m = 0
for j,k in enumerate(a):
if i % a[j] == 0 and i not in a:
m = 0
break
if i % a[j] != 0:
m += 1
if m >= 1:
a.append(i)
yield i
i += 1
Could you please share some pointers with me to make the code run faster.
python generator primes yield execution-time
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
asked Nov 10 at 15:56
Pandora-Box
183
This question already has an answer here:
Fastest way to list all primes below N
30 answers
Simple Prime Generator in Python
22 answers
I created a sample code in python with yield.
I am trying to fine tune this code below to be a bit more efficient in execution time.
def gen_prime():
a =
i = 2
j = 1
m = 0
while True:
if i == 2:
a.append(i)
yield i
m = 0
for j,k in enumerate(a):
if i % a[j] == 0 and i not in a:
m = 0
break
if i % a[j] != 0:
m += 1
if m >= 1:
a.append(i)
yield i
i += 1
Could you please share some pointers with me to make the code run faster.
This question already has an answer here:
Fastest way to list all primes below N
30 answers
Simple Prime Generator in Python
22 answers
python generator primes yield execution-time
python generator primes yield execution-time
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
asked Nov 10 at 15:56
Pandora-Box
183
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
asked Nov 10 at 15:56
Pandora-Box
183
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
edited Nov 10 at 17:29
Matthieu Brucher
5,7511228
5,7511228
asked Nov 10 at 15:56
Pandora-Box
183
asked Nov 10 at 15:56
Pandora-Box
183
asked Nov 10 at 15:56
Pandora-Box
183
183
marked as duplicate by Daniel Mesejo, jonrsharpe, Austin Hastings, Håken Lid, James K Polk Nov 11 at 2:34
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Daniel Mesejo, jonrsharpe, Austin Hastings, Håken Lid, James K Polk Nov 11 at 2:34
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
Because you are looking for improvements to working code, I'll suggest that you might want to submit this to Code Review instead.
– Austin Hastings
Nov 10 at 16:01
If you moveyield 2before the loop and start ati = 3, you can remove thei not in acheck. Also, no need to useenumerate; just usekinstead ofa[j]. You don’t need to checkif i % a[j] != 0. Using actual names likeprimesinstead of single letters likeawill help with readability.
– Ry-♦
Nov 10 at 16:02
stop the enumeration at the sqrt of i.
– Will Ness
Nov 10 at 18:24
add a comment |
1
Because you are looking for improvements to working code, I'll suggest that you might want to submit this to Code Review instead.
– Austin Hastings
Nov 10 at 16:01
If you moveyield 2before the loop and start ati = 3, you can remove thei not in acheck. Also, no need to useenumerate; just usekinstead ofa[j]. You don’t need to checkif i % a[j] != 0. Using actual names likeprimesinstead of single letters likeawill help with readability.
– Ry-♦
Nov 10 at 16:02
stop the enumeration at the sqrt of i.
– Will Ness
Nov 10 at 18:24
1
1
Because you are looking for improvements to working code, I'll suggest that you might want to submit this to Code Review instead.
– Austin Hastings
Nov 10 at 16:01
Because you are looking for improvements to working code, I'll suggest that you might want to submit this to Code Review instead.
– Austin Hastings
Nov 10 at 16:01
If you move
yield 2 before the loop and start at i = 3, you can remove the i not in a check. Also, no need to use enumerate; just use k instead of a[j]. You don’t need to check if i % a[j] != 0. Using actual names like primes instead of single letters like a will help with readability.– Ry-♦
Nov 10 at 16:02
If you move
yield 2 before the loop and start at i = 3, you can remove the i not in a check. Also, no need to use enumerate; just use k instead of a[j]. You don’t need to check if i % a[j] != 0. Using actual names like primes instead of single letters like a will help with readability.– Ry-♦
Nov 10 at 16:02
stop the enumeration at the sqrt of i.
– Will Ness
Nov 10 at 18:24
stop the enumeration at the sqrt of i.
– Will Ness
Nov 10 at 18:24
add a comment |
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
I think if all you want to do is generating prime numbers, your code is over-complicated. Here's a simpler approach.
EDIT: As @WillNess pointed out, it is sufficient to check up to square root of the given number. More on why can be found here and here.
EDIT2: As @WillNess and @Ross pointed out in comments, we may firstly yield 2 (since it is the only even prime) and then count in 2s while keeping a list of primes and trying to to divide only by primes. The code is now slightly more complicated but a lot more efficient. I've added comments to the code to make sure everything is as clear as a crystal:
from math import sqrt # only checking up to sqrt(numb)
def gen_prime():
yield 2 # get 2 out of the way
primes = [2] # list of primes
numb = 1
while(True):
flag = False # True means prime, False not a prime
numb += 2 # counting in 2s because no even number other than `2` is a prime
for div in primes: # trying only primes
if (div > sqrt(numb)): # if `div` is greater than sqrt(numb), every other element in the list after `div` also is greater, thus the number is a prime
flag = True # we set the flag true
break # and get out of the loop
if (numb % div == 0): # if `numb` is dividable by any of the elements in the list, it is not a prime,
break # we don't change the flag and get out of the loop
if(flag): # if the flag is `True`
primes.append(numb) # we add this number to the list of primes
yield numb # and yield it
Thanks again to @WillNess and @Ross for their contributions
answered Nov 10 at 16:18
Ayxan
94814
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
The algorithm is still good, but you search for too many numbers. Letting therangego tosqrt(numb)is enough
– user8408080
Nov 10 at 17:59
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
Another simple optimization is that since 2 is the only even prime, you can just add ayield 2at the top of the method, and then count up in 2s and start your div range at 3.
– Ross
Nov 10 at 18:16
|
show 4 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
I think if all you want to do is generating prime numbers, your code is over-complicated. Here's a simpler approach.
EDIT: As @WillNess pointed out, it is sufficient to check up to square root of the given number. More on why can be found here and here.
EDIT2: As @WillNess and @Ross pointed out in comments, we may firstly yield 2 (since it is the only even prime) and then count in 2s while keeping a list of primes and trying to to divide only by primes. The code is now slightly more complicated but a lot more efficient. I've added comments to the code to make sure everything is as clear as a crystal:
from math import sqrt # only checking up to sqrt(numb)
def gen_prime():
yield 2 # get 2 out of the way
primes = [2] # list of primes
numb = 1
while(True):
flag = False # True means prime, False not a prime
numb += 2 # counting in 2s because no even number other than `2` is a prime
for div in primes: # trying only primes
if (div > sqrt(numb)): # if `div` is greater than sqrt(numb), every other element in the list after `div` also is greater, thus the number is a prime
flag = True # we set the flag true
break # and get out of the loop
if (numb % div == 0): # if `numb` is dividable by any of the elements in the list, it is not a prime,
break # we don't change the flag and get out of the loop
if(flag): # if the flag is `True`
primes.append(numb) # we add this number to the list of primes
yield numb # and yield it
Thanks again to @WillNess and @Ross for their contributions
answered Nov 10 at 16:18
Ayxan
94814
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
The algorithm is still good, but you search for too many numbers. Letting therangego tosqrt(numb)is enough
– user8408080
Nov 10 at 17:59
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
Another simple optimization is that since 2 is the only even prime, you can just add ayield 2at the top of the method, and then count up in 2s and start your div range at 3.
– Ross
Nov 10 at 18:16
|
show 4 more comments
up vote
4
down vote
accepted
I think if all you want to do is generating prime numbers, your code is over-complicated. Here's a simpler approach.
EDIT: As @WillNess pointed out, it is sufficient to check up to square root of the given number. More on why can be found here and here.
EDIT2: As @WillNess and @Ross pointed out in comments, we may firstly yield 2 (since it is the only even prime) and then count in 2s while keeping a list of primes and trying to to divide only by primes. The code is now slightly more complicated but a lot more efficient. I've added comments to the code to make sure everything is as clear as a crystal:
from math import sqrt # only checking up to sqrt(numb)
def gen_prime():
yield 2 # get 2 out of the way
primes = [2] # list of primes
numb = 1
while(True):
flag = False # True means prime, False not a prime
numb += 2 # counting in 2s because no even number other than `2` is a prime
for div in primes: # trying only primes
if (div > sqrt(numb)): # if `div` is greater than sqrt(numb), every other element in the list after `div` also is greater, thus the number is a prime
flag = True # we set the flag true
break # and get out of the loop
if (numb % div == 0): # if `numb` is dividable by any of the elements in the list, it is not a prime,
break # we don't change the flag and get out of the loop
if(flag): # if the flag is `True`
primes.append(numb) # we add this number to the list of primes
yield numb # and yield it
Thanks again to @WillNess and @Ross for their contributions
answered Nov 10 at 16:18
Ayxan
94814
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
The algorithm is still good, but you search for too many numbers. Letting therangego tosqrt(numb)is enough
– user8408080
Nov 10 at 17:59
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
Another simple optimization is that since 2 is the only even prime, you can just add ayield 2at the top of the method, and then count up in 2s and start your div range at 3.
– Ross
Nov 10 at 18:16
|
show 4 more comments
up vote
4
down vote
accepted
up vote
4
down vote
accepted
I think if all you want to do is generating prime numbers, your code is over-complicated. Here's a simpler approach.
EDIT: As @WillNess pointed out, it is sufficient to check up to square root of the given number. More on why can be found here and here.
EDIT2: As @WillNess and @Ross pointed out in comments, we may firstly yield 2 (since it is the only even prime) and then count in 2s while keeping a list of primes and trying to to divide only by primes. The code is now slightly more complicated but a lot more efficient. I've added comments to the code to make sure everything is as clear as a crystal:
from math import sqrt # only checking up to sqrt(numb)
def gen_prime():
yield 2 # get 2 out of the way
primes = [2] # list of primes
numb = 1
while(True):
flag = False # True means prime, False not a prime
numb += 2 # counting in 2s because no even number other than `2` is a prime
for div in primes: # trying only primes
if (div > sqrt(numb)): # if `div` is greater than sqrt(numb), every other element in the list after `div` also is greater, thus the number is a prime
flag = True # we set the flag true
break # and get out of the loop
if (numb % div == 0): # if `numb` is dividable by any of the elements in the list, it is not a prime,
break # we don't change the flag and get out of the loop
if(flag): # if the flag is `True`
primes.append(numb) # we add this number to the list of primes
yield numb # and yield it
Thanks again to @WillNess and @Ross for their contributions
answered Nov 10 at 16:18
Ayxan
94814
I think if all you want to do is generating prime numbers, your code is over-complicated. Here's a simpler approach.
EDIT: As @WillNess pointed out, it is sufficient to check up to square root of the given number. More on why can be found here and here.
EDIT2: As @WillNess and @Ross pointed out in comments, we may firstly yield 2 (since it is the only even prime) and then count in 2s while keeping a list of primes and trying to to divide only by primes. The code is now slightly more complicated but a lot more efficient. I've added comments to the code to make sure everything is as clear as a crystal:
from math import sqrt # only checking up to sqrt(numb)
def gen_prime():
yield 2 # get 2 out of the way
primes = [2] # list of primes
numb = 1
while(True):
flag = False # True means prime, False not a prime
numb += 2 # counting in 2s because no even number other than `2` is a prime
for div in primes: # trying only primes
if (div > sqrt(numb)): # if `div` is greater than sqrt(numb), every other element in the list after `div` also is greater, thus the number is a prime
flag = True # we set the flag true
break # and get out of the loop
if (numb % div == 0): # if `numb` is dividable by any of the elements in the list, it is not a prime,
break # we don't change the flag and get out of the loop
if(flag): # if the flag is `True`
primes.append(numb) # we add this number to the list of primes
yield numb # and yield it
Thanks again to @WillNess and @Ross for their contributions
answered Nov 10 at 16:18
Ayxan
94814
edited Nov 10 at 19:32
answered Nov 10 at 16:18
Ayxan
94814
answered Nov 10 at 16:18
Ayxan
94814
answered Nov 10 at 16:18
Ayxan
94814
94814
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
The algorithm is still good, but you search for too many numbers. Letting therangego tosqrt(numb)is enough
– user8408080
Nov 10 at 17:59
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
Another simple optimization is that since 2 is the only even prime, you can just add ayield 2at the top of the method, and then count up in 2s and start your div range at 3.
– Ross
Nov 10 at 18:16
|
show 4 more comments
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
The algorithm is still good, but you search for too many numbers. Letting therangego tosqrt(numb)is enough
– user8408080
Nov 10 at 17:59
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
Another simple optimization is that since 2 is the only even prime, you can just add ayield 2at the top of the method, and then count up in 2s and start your div range at 3.
– Ross
Nov 10 at 18:16
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
Thanks Ares it did help me :)
– Pandora-Box
Nov 10 at 16:27
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
the single most voted answer in the primes tag disagrees with your approach.
– Will Ness
Nov 10 at 17:40
The algorithm is still good, but you search for too many numbers. Letting the
range go to sqrt(numb) is enough– user8408080
Nov 10 at 17:59
The algorithm is still good, but you search for too many numbers. Letting the
range go to sqrt(numb) is enough– user8408080
Nov 10 at 17:59
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
@WillNess Thanks for your contribution! Edited and added.
– Ayxan
Nov 10 at 18:00
Another simple optimization is that since 2 is the only even prime, you can just add a
yield 2 at the top of the method, and then count up in 2s and start your div range at 3.– Ross
Nov 10 at 18:16
Another simple optimization is that since 2 is the only even prime, you can just add a
yield 2 at the top of the method, and then count up in 2s and start your div range at 3.– Ross
Nov 10 at 18:16
|
show 4 more comments
1
Because you are looking for improvements to working code, I'll suggest that you might want to submit this to Code Review instead.
– Austin Hastings
Nov 10 at 16:01
If you move
yield 2before the loop and start ati = 3, you can remove thei not in acheck. Also, no need to useenumerate; just usekinstead ofa[j]. You don’t need to checkif i % a[j] != 0. Using actual names likeprimesinstead of single letters likeawill help with readability.– Ry-♦
Nov 10 at 16:02
stop the enumeration at the sqrt of i.
– Will Ness
Nov 10 at 18:24