I'm not too sure I understood the question entirely (sorry if I didn't, I'll remove the answer if it's not helpful) but maybe the bisect module (which only works on sorted lists, but that if works, it's pretty fast) would be of some help in this case:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect
import math
primes = [2,3,5,7]
searchedPrime=11
lookedPosition = 1 + int(math.sqrt(searchedPrime))
checkUntil = primes[:bisect.bisect_left(primes, lookedPosition)]
print "I just have to check %s positions: %s" % (len(checkUntil), checkUntil)
This outputs
I just have to check 2 positions: [2, 3]
So maybe a combination of the sqrt
method and the bisect tools will help you determine the range of primes to check.
Edit:
Oh, look at that... I didn't know that the sqrt thing was suitable to find prime numbers... but it looks like it is...
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect
import math
foundPrimes = []
def isPrime(number, otherPrimes):
global foundPrimes
lookedPosition = 1 + int(math.sqrt(number))
formerPrimes = foundPrimes[:bisect.bisect_left(foundPrimes, lookedPosition)]
for prime in formerPrimes:
if prime > 1 and number % prime == 0:
return False
return True
def getPrimes(upperLimit):
for i in range(1, upperLimit):
if isPrime(i, foundPrimes):
foundPrimes.append(i)
return foundPrimes
print "Primes: %s" % getPrimes(1000)
This outputs:
Primes: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
... which look pretty primy to me... :-)
P.S.: Don't use that code like that... it's crap.