Welcome, guest | Sign In | My Account | Store | Cart

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)

Python, 47 lines
 1
 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)

3 comments

edrichdrich 13 years, 9 months ago  # | flag

This algorithm it isn't fast enough but at least it is based in a clever idea ... Well done !!!

Dieter Kadelka 13 years, 9 months ago  # | flag

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.

Giannis Fysakis (author) 13 years, 9 months ago  # | flag

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 ...