20180516, 18:51  #1  
Dec 2017
2^{4}·3·5 Posts 
"Genius" needed to speed up this notevenasieve in Python but he did not succeed
I need help regarding a Mersenne Prime Sieve which I edited to perform this task; this code is from a perfect number generator. The problem is the program slows down at 11213 in python. Can anyone offer some speed enhancements for this sieve in Python? The output starts out like this.
Quote:
Code:
from itertools import count def postponed_sieve(): # postponed sieve, by Will Ness yield 2; yield 3; yield 5; yield 7; # original code David Eppstein, sieve = {} # Alex Martelli, ActiveState Recipe 2002 ps = postponed_sieve() # a separate base Primes Supply: p = next(ps) and next(ps) # (3) a Prime to add to dict q = p*p # (9) its sQuare for c in count(9,2): # the Candidate if c in sieve: # c's a multiple of some base prime s = sieve.pop(c) # i.e. a composite ; or elif c < q: yield c # a prime continue else: # (c==q): # or the next base prime's square: s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...) p=next(ps) # (5) q=p*p # (25) for m in s: # the next multiple if m not in sieve: # no duplicates break sieve[m] = s # original test entry: ideone.com/WFv4f def prime_sieve(): # postponed sieve, by Will Ness yield 2; yield 3; yield 5; yield 7; # original code David Eppstein, sieve = {} # Alex Martelli, ActiveState Recipe 2002 ps = postponed_sieve() # a separate base Primes Supply: p = next(ps) and next(ps) # (3) a Prime to add to dict q = p*p # (9) its sQuare for c in count(9,2): # the Candidate if c in sieve: # c’s a multiple of some base prime s = sieve.pop(c) # i.e. a composite ; or elif c < q: yield c # a prime continue else: # (c==q): # or the next base prime’s square: s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...) p=next(ps) # (5) q=p*p # (25) for m in s: # the next multiple if m not in sieve: # no duplicates break sieve[m] = s # original test entry: ideone.com/WFv4f def mod_mersenne(n, prime, mersenne_prime): while n > mersenne_prime: n = (n & mersenne_prime) + (n >> prime) if n == mersenne_prime: return 0 return n def is_mersenne_prime(prime, mersenne_prime): s = 4 for i in range(prime  2): s = mod_mersenne((s*s  2), prime, mersenne_prime) return s == 0 def calculate_perfects(): yield(2) primes = prime_sieve() next(primes) #2 is barely even a prime for prime in primes: if is_mersenne_prime(prime, 2**prime1): yield(prime) if __name__ == '__main__': for perfect in calculate_perfects(): print(perfect) #edited by Tom E.O'Neil to find Mprimes 

20180517, 21:19  #2 
Dec 2017
2^{4}×3×5 Posts 
you can see it in action here:
Hit run once its done loading. https://repl.it/@TommyONeil/HumongousRubberyElements Last fiddled with by Uncwilly on 20180517 at 22:10 Reason: Made link unclickable. 
20180517, 22:11  #3 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
3^{2}·1,019 Posts 
I have again made a link of your's, not a hyperlink. The user needs to be more involved before you your code on their machine.

20180517, 23:33  #4 
Dec 2017
11110000_{2} Posts 

20180518, 02:02  #5  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
21723_{8} Posts 
Quote:
Linking directly to an exe or to page that runs code is not ok. When I previously told you about this you failed to understand where problems could pop up. 

20180518, 19:26  #6 
Dec 2016
2×3^{3} Posts 
The first step would be to know which part of your code needs to be optimized. Use Python's profiler to figure out where your code spends most of its time, then focus on that code.

20180518, 19:28  #7 
"Mark"
Apr 2003
Between here and the
6162_{10} Posts 
I suggest that you learn a language like C if you want speed.

20180519, 05:48  #8 
Romulan Interpreter
Jun 2011
Thailand
3×17×179 Posts 
@op: additional of what other people told you in the past about demonstrating your knowledge (or... ignorance) not only about math but also about programming, here you also proved that you don't know what a "sieve" is. This is not a sieve, it is an (extremely slow) program that finds mersenne primes. You use some wheel to find primes, then do LL test for each prime to see if the corespondent mersenne is itself prime. But you can not use the information to "sieve" anything with it. It should be nice if you could "sieve" the prime exponents in such a way to avoid doing at least few percents of the LL tests, even one percent of them, then THAT should have been A RESULT. Please note the uppercase letters. This what you show is crap.
Last fiddled with by LaurV on 20180519 at 05:50 
20180519, 08:36  #9  
Dec 2017
2^{4}×3×5 Posts 
Quote:


20180519, 09:28  #10  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3^{4}·37 Posts 
Quote:
You have implemented the well known LL test in a scripting language. We have all done that at some point just to get a feel for how things work. But it is not something important enough to post to a public board and expect everyone else to "improve" it for you. If you are really serious about it, learn about FFT and/or NTT (or preferably invent a new faster method) and implement the test in optimised assembly on your favourite highperformance CPU. THEN you will get some attention for doing something important. 

20180519, 11:46  #11 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
any suitable sieve written in C or Python?  Shen  Information & Answers  4  20170105 04:49 
Sieve needed for a^(2^b)+(a+1)^(2^b)  robert44444uk  Software  55  20090812 06:39 
Sieve needed for k*b1^m*b2^n+1  beyastard  Software  55  20090729 12:51 
Volunteer needed for sieve merging  MooooMoo  Twin Prime Search  9  20070101 21:13 
Pentium4 2.8Ghz speed help needed  Clyde83  Hardware  26  20060821 10:33 