Faster primality testing?

Question

I have to make a list of primes, and I found out that all primes are of the form 6n+1 or 6n+5 (however not all numbers of this form are prime). Thus, I use it to find primes more quickly as such:

is_prime(n):
   for all i <= sqrt(n)
       if i divides n: return False
   return n >= 2

generate_prime(past_prime):
    // Since we know the past prime is already of the form 6n+1 or 6n+5, we just need to add either 4 or 2 respectively to get to the next candidate prime

    if past_prime mod 6 is 1: past_prime += 4 // Moves from 6n+1 to 6n+5
    else: past_prime += 2 // Moves from 6n+5 to 6n+7->6(n+1)+1

    while(True):
        if(is_prime(past_prime)):
            return past_prime
        if past_prime mod 6 is 1: past_prime += 4 
        else: past_prime += 2 

What would be the speed of this algorithm (in terms of big O)? How would it compare to other deterministic methods like the sieve Erasthones?

Answer 1

This is roughly O(log(n)*sqrt(n)) since the odds of a number being prime are roughly 1/log(n) and your isprime is roughly O(sqrt(n)). The main improvement here is to use a much faster is_prime function. Instead you can use something like Baillie-PSW which has runtime of O(log(n)^k) for some fairly small k. This optimization will make your code a few orders of magnitude faster for large inputs.