Okay so anybody that has done any research into finding prime numbers has probably gone to the wikipedia page and seen this:
(https://rmrk.net/proxy.php?request=http%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fc%2Fc8%2FAnimation_Sieve_of_Eratosth-2.gif&hash=efcc5fdb775a852e0b262da7b5712ce3b3a464ee)
It is the Sieve of Eratosthenes algorithm which finds all primes to a specified integer. Basically a prime is a number which is 1,2,3,5,7 or indivisible by 2,3,5 and 7. This comes useful at programming competitions. ;] Now before today I had given very little thought to the existence of a pattern in the spacing of primes on the number line but yesterday I started playing with python again and thought I'd give it a go. And I found it. The pattern between the first 6 is 1,1,1,2,2,4 and the patern which is repeated to infinity is 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10. 48 numbers which are continuously added to a sum to find the nth prime. Now I tested this up the the 1,000,000th prime and it works. Here was my original function for finding the nth prime number (in Python)
def nth_prime(n):
y = [1, 1, 1, 2, 2, 4]
x = [2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4]
a,b=0,0
while a<n:
if b<11:
b+=y[a%6]
else:
b+=x[a%48]
a+=1
return b
This gets pretty inefficient and time consuming when dealing with numbers bigger than 10^6 so I wrote this
def nth_prime(n):
y = [1, 1, 1, 2, 2, 4]
x = [2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4]
a,b=0,0
while a<n:
if b<11:
b+=y[a%6]
elif n-a>48:
b,a=b+((n//48)*210),a+(n//48)
else:
b+=x[a%48]
a+=1
return b
which basically just takes the time and throws it in a blender. I was able to verify the 10^14th prime in a split second.
So yeah, if you ever need to find the nth prime and are familiar with Python you can feel to implement this. Just please if it's anything official comment my name into the function def (Logan Blackburn).
Let me know what you think!
I think I need an aspirin.
Irock dum dum
Did you write that in Python?
I might swap that into C++ and use it if I ever need a prime number.
though it's hard to figure out when I'd ever need it.
It's nice to see you experimenting ^_^
Unfortunately your method is not sound. Putting n = 32 gives you 121 which is 11 squared.
*hugs*
You got Zeriabowned ._.
I did this for some of my course they had an optional activity to make a list of prime numbers, It worked but no one else did it and it didnt count towards my mark :(
Nice try, though. I could never try something like this. :P