Is this a worthwhile Prime Number Generator?

77 Views Asked by At

So I wrote a little bit of MatLAB to try to exponentially generate larger and larger primes. The main draw back is that because it is exponentially generating larger primes it will miss a lot of prime numbers in between the ones it finds. So I use the MATLab isprime() method to perform a primality test instead of rel.

Without the isprime() method the code will fail after generating 319 as the numbers 11 and 29 would not have been generated. With the isprime() method it gets to a prime on the order of 3e12 within seconds.

Has anyone seen an algorithm like this before? I had kind of thought I saw a pattern and went out to see if my algorithim would work. It did, just not as well as I would like.

Sorry if this isn't the right place to post this. I didn't really know where else to.

prime_list(1) = 2;  %this list size will grow with more primes
count = 0;          %this is counting distance of next prime to the nth found prime in the list
iterate = 1;        %this is for index through the prime_list
sub_count = 0;      %this is a for one of the prime generation fall back methods

while 1
    pass = 1;
    count_temp = count;

    %see if the next prime is 2*largest_prime-1, primary method of generating an exponentially larger prime

    for j = 1 : length(prime_list)
        if rem(count(j)+prime_list(iterate)-1,prime_list(j)) == 0
            pass = 0;
        else
            count_temp(j) = count(j) + prime_list(iterate)-1;
        end
    end

    %double check, fall back method because of gaps in primes
    if(isprime(2*prime_list(iterate)-1))
        pass = 1;
    else
        pass = 0;
    end

    %if it is a prime update the lists
    if pass
        iterate = iterate+1;
        prime_list(iterate) = 2*prime_list(iterate-1)-1;
        count = count_temp;
        count(iterate) = 0;
    else
        %if it wasn't, start from the largest found prime and look for the next prime one increment at a time (fall back method)
        pass2 = 0;
        while pass2 == 0
            while pass == 0
                pass = 1;
                count = count+1;
                sub_count = sub_count+1;
                for j = 1 : length(prime_list)
                    if rem(count(j),prime_list(j)) == 0
                        pass = 0;
                    end
                end
            end

            %double check if it really is a prime

            if(isprime(prime_list(iterate)+sub_count))
                pass2 = 1;
            else
                pass = 0;
            end
        end

        %once it is found to be prime, update the lists
        iterate = iterate+1;
        prime_list(iterate) = prime_list(iterate-1)+sub_count;
        count(iterate) = 0;
        sub_count = 0;
    end
end