Ultra Fast Prime number generating algorithm : optimized knuth's theorem

heyy folks,
this is sudden yeah and i'll explain why and how. Only yesterday I got a strange wall post on google plus from a friend of mine. It said "Extended Wilson Theorem". Naturally i was curious and I started reading that link [from his blog] and the rest of the articles about prime numbers.
http://mathematicswithvidura.blogspot.com/

( BIG THANK TO Vidura for putting this into ma attension :) )

Then I found this article which says about the 6m ± 1 theory. It says that

Every prime number except 2 and 3 can be expressed in the form 6m ± 1BUT not ALL numbers that can be expressed as above are primes.

And then I was thinking along the line of increasing the efficiency of prime number generation using this, since I always get stuck in trying to generate huge lists of prime numbers. So I generated a few 6m ± 1 numbers and observed its properties.


m       6m-1       6m+1

1       5            7
2       11          13
3       17          19
4       23          25
.
.
.
16       95          97
.
.
.
40       239         241

see the red ones? those the NON primes when applied to that number sequence,
so here are those numbers in a list, and a factor of them are listed, and GUESS WHAT?

25  -> 5
35  -> 5
49  -> 7
55  -> 5
65  -> 5
77  -> 7
.
.
.
125  -> 5
133  -> 7

ALL of these numbers have a PRIME NUMBER as one of it's factors other than itself and one :D

Hell yeah, so i formulated this hypothesis which I cannot prove mathematically at the moment.
NOTE: I dont know whether this was proven beforehand, but i only found this today, so my apologies for lack of knowledge whether this is already proven or not

When m takes different values of the expression, E = 6m ± 1 , E gives prime numbers or composite numbers that have prime numbers as one or more of its factors

So need not to say that using this we can speed up the prime generation pretty pretty fast

NOTE:
I only got to know about Knut's algorithm later, as it seems it clearly says that

1. 
   

if n is prime, it's not divisible by any prime number upto squareroot(n)

which is as same as mine, so this ISNT a new algo, it's same as Knuts, but still worth looking on it

EDIT:
On a later notice, this is actally 3x faster than Knuth's due to the use of 6m ± 1 rule

Prime Generation Algorithms compared

1) Naiive

Lets look at the textbook way of generatin primes

1. lim -> the upper limit upto which the primes whould be generated
   S   -> set of all prime numbers found
   loop i = 1 to lim
2.         if i == 1 : continue
3.         if i==2 or i==3
4.                   S.add(i)
5.                   continue;
7.          isPrime = true        
8.          loop j = 2 to sqrt(i)
9.                       if j%i == 0
10.                               isPrime = false
11.                               break;
12.          end loop
13.          if isPrime : S.add(i)
14. end loop

Now considering the running time of this algorithm,
if the upper limit is N
this would take approximately O(N^2) time complexity considering all factors

2) Using the above hypothesis

1. lim -> the upper limit upto which the primes whould be generated
2. S   -> set of all prime numbers found
4. if lim > 2 : S.add(2)
5. if lim > 3 : S.add(3)
7. loop i = 1 to ...
8.         //now we dont check ALL numbers, just the ones according to 6m +/- 1 theory
9.         n -> 6*m - 1
10.        
11.         //if the value is larger than the limit we stop
12.         if n > lim : break
13.        
14.         if isPrime(n) : S.add(n)
15.        
16.         n -> n+2
17.        
18.         if isPrime(n) : S.add(n)
19. end loop
20.        
21.        
22.        
23. function isPrime(n)
24.         //we will check whether a prime from our generated list is a factor of n
25.         sq = sqrt(n)
26.        
27.         loop each element i in S:
28.                 //we only need to check till i<=sq
29.                 if i > sq : break
30.                
31.                 if n%i == 0
32.                         return false
33.         end loop
34.        
35.         return true
36. end function

so, given this we can actually bring down the time complexity to
O(N*sqrt(N)/6)
but since sqrt(N) <<<<< N for very large values AND no of primes below a very large number is considerably low,

rephrasing:
lets consider finding whether there's a factor for a number of range 10^8
the normal algorithm will loop over sqrt(N) times that's 10^4 times
but since we are looping only over our previously collected collection of primes
and there's only 1229 primes below 10^4, we loop only 1229 time

see the difference? :)
but since sqrt(N) <<<<< N for very large values AND no of primes below a very large number is considerably low,
we can say it's O(N) for very large numbers
of course i cant prove this yet, but i'm running the codes at the moment, so as sooon as i get positive [or negative] results i'll update it here :)