I was wondering if there is way to slice an existing list to a certain number that is most likely not in the list. For example, suppose I have:
primes = [2,3,5,7]
Now I want to test the number 11 for primness. I will do so by trial division by all the primes, under the limit of 1 + integer square root of 11. So instead of looping through all elements of the list, primes and breaking the loop once the elements are larger than the limit, I was wondering if I could splice the list to value of Limit. In this case, the value would be :
1 + int(sqrt(11)) = 1 + 3 = 4
so i can loop over elements of primes[ : up until the value of 4]
or [2,3]
I know some deal of python, but I am not sure on how to do this with just list methods... And for sieve methods up to the billions, I could efficiently save time by not using if statements...
Thanks again in advance!
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.
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.