Skip to content

Instantly share code, notes, and snippets.

@markhamilton1
Created March 23, 2014 00:55
Show Gist options
  • Save markhamilton1/9716776 to your computer and use it in GitHub Desktop.
Save markhamilton1/9716776 to your computer and use it in GitHub Desktop.
prime is a Python script that calculates prime numbers and then looks for prime types.
"""
Functions:
calc - calculate the specified number of primes starting with 2
findTypes - find the types in the current list of primes
"""
from math import sqrt
primeList = [2]
gapList = []
typeList = []
"""
Calculate the first n primes.
In:
n = number of primes to calculate
"""
def calc(n=1000):
global primeList
global gapList
lastPrime = 2
primeList = [lastPrime]
gapList = []
num = 3
isPrime = 1
while len(primeList) < n:
sqrtNum = sqrt(num)
for primeNumber in primeList:
if num % primeNumber == 0:
isPrime = 0
break
if primeNumber > sqrtNum:
break
if isPrime == 1:
primeList.append(num)
gapList.append(num - lastPrime)
lastPrime = num
else:
isPrime = 1
num += 2
"""
Find "prime types" with the specified parameters.
A "prime type" is a sequence of n primes, each within maxGap of
the next prime in the type.
In:
n = number of primes in type
maxGap = maximum difference between each consecutive prime in type
"""
def findTypes(n=2, maxGap=2):
global primeList
global gapList
global typeList
typeList = []
idx = 0
while idx + n - 1 < len(gapList):
primeType = [primeList[idx]]
isType = 1
for i in xrange(0, n - 1):
primeType.append(primeList[idx + i + 1])
if gapList[idx + i] > maxGap:
isType = 0
break
if isType == 1:
typeList.append(primeType)
idx += 1
calc()
print "# of primes: %i" % len(primeList)
print primeList
findTypes()
print "# of types found: %i" % len(typeList)
print typeList
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment