The algorithm is based on the idea
that the next larger prime after one prime is the sum of the two smaller previous minus three prime numbers back.
For the first five prime numbers 2,3,5,7,11 this pattern is not true also it is not true if the number is a composite number (including of course if the number's square root is integer).
Example trying to find the tenth prime
so lets play with numbers 17(minus 3 from Next,position 7), 19(minus 2 from Next,position 8), 23(minus 1 from Next,position 9) and number Next at position 10 :
hmmm ... if we add 19 and 23 we get 42, but 42 minus 17 equals 25 which isn't a prime :(
In order to correct this we assume that 25 is the next prime number ( temporary holding the tenth position) finally to get the real Next prime number we take 23 + 25 = 48 , we subtract 19 and we get 29 which finally it takes the tenth position ( because it deserves it :P)
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | def filterout(L1,L2):
""" inplace substraction of two lists"""
for i in L1:
if i in L2:
L2.remove(i)
def is_prime(n):
""" check if n is prime"""
i = 2
if n <=1:
return False
Sqrt_Of_n = n**0.5
while i <= Sqrt_Of_n:
if n % i == 0:
return False
i += 1
else:
return True
def primeGen(n):
"""
After the first 5 primes the next prime number is the sum of the last 2
minus the three prime numbers back
if it is not a prime number we go for the next one
"""
primes= [2,3,5,7,11]
if n in xrange(1,len(primes)+1):
return primes[:n]
else:
banlist=[]
count = 6
while count <= n :
Next = (primes[-2] + primes[-1]) - primes[-3]
if not is_prime(Next):
count -=1
banlist.append(Next)
count +=1
primes.append(Next)
filterout(banlist,primes)
return primes
if __name__ == '__main__':
print primeGen(1000)
|
I tried to find a way to generate some primes, my intention wasn't the speed, i only wanted to show a different possible approach for finding primes... although i think even a bad implementation of the sieve of Eratosthenes can be a lot faster i enjoyed making this piece of code .
I have compared the results until the first 1000 primes with these http://primes.utm.edu/lists/small/1000.txt and it is correct . so i assume that it will be correct for all the primes...
I haven't seen this algorithm anywhere else so i also assume that i 've invented it :-)
Please feel free to give advise , opinions on that :-) ( and if you have seen this else where please give me a link and i correct the licence if it is necessary)
This algorithm it isn't fast enough but at least it is based in a clever idea ... Well done !!!
Sorry, the idea is not clever. The algorithm accidentally is correct, since primes contains any number >= 13 and not divisible by 2 or 3. If you start with primes = [2,3,...,29,31,37] the you miss the prime number 43.
Dieter Kadelka
It's true ,it won't find 43 if it starts with the first 12 primes as a starting point (2..37). As a matter of fact (as i mentioned above ) it only works starting off with the exactly first 5 primes ( 2,3,5,7,11 ). That's the conditions that the algorithm works , it doesn't work with all possible combinations of prime numbers starting points.
Note that if you start with the first primes up to 53 (2..53) it ignores many more primes from the results...
I test it with the first 10000 Primes and it is correct (http://primes.utm.edu/lists/small/10000.txt) The problem is that it is slow... the time complexity grows exponentially... and i feel that it's "cleverness" fades out due to the fact of being slow...
Anyway i enjoyed that code ,but i am pretty sure that if i need prime numbers i 'll fall back to the faster and better solutions of known prime number generators ...