I've made a sieve for generating primes. I'm doing a school project about RSA which includes some programming. I'll use the primes for an RSA system, but because it's for my essay the security isn't really important. However, big primes are much more challenging and I like that. The code I use:
def Zeef(a):
import math
upperBound = a
upperBoundSquareRoot = int(math.sqrt(upperBound))
isPrime = [1 for m in range (0,upperBound+1)]
for m in range(2,upperBoundSquareRoot+1):
if (isPrime[m]==1):
for k in range(m*m,upperBound+1,m):
isPrime[k] = 0;
print("Priemgetallen : ")
numberofPrimes = 0
for m in range(2,upperBound+1):
if (isPrime[m] ==1):
print(m)
numberofPrimes = numberofPrimes+1
print("Aantal = " , numberofPrimes);
a=input("Alle priemgetallen tot: ")
aa=int(a)
Priemen = Zeef(aa)
I'm sure there is a faster way for generating primes, but i'm not really interested in improving my code right now.
When I'm running this function, it works fine for generating primes up to 7 digits, but when I want more, it's really slow. My computer (8gb ram) gives a message that there's not enough memory. I used the same algoritm in Processing, an other tool. Processing is really quick, but it doesn't recognize more than 10 digits. I also noticed the printing is slow when I'm generating primes which my computer is able to calculate.
I began searching on the internet and i found that i compiling my program would speed up the progress, but i'm not sure if it speeds up the calculation and printing part or just the interpreting part. I also found something about numpy wich was about arrays, but I'm not sure if this will notably speeds up my function.
How can I find my primes faster?
You will need a better algorithm than the Sieve of Eratosthenes if you want to generate the kinds of large prime numbers needed for the RSA algorithm. Here's an implementation of the Miller-Rabin primality checker for Python:
def isPrime(n):
def isSpsp(n, a):
d, s = n - 1, 0
while d % 2 == 0: d, s = d / 2, s + 1
t = pow(a, d, n)
if t == 1: return True
while s > 0:
if t == n - 1: return True
t, s = (t * t) % n, s - 1
return False
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
if n in ps: return True
for p in ps:
if not isSpsp(n, p): return False
return True
If you're interested in programming with prime numbers, I modestly recommend this essay at my blog; you might also look at some of the other pages at my blog, including this one on generating RSA semi-primes.