Python: How to slice a list to a certain value

Question

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!

Answer 1

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.

Answer 2

[i for i in primes if i < 4]

Answer 3

Maybe itertools.takewhile

>>> from itertools import takewhile
>>> primes
[2, 3, 5, 7]
>>> b = takewhile(lambda k : k < 4, primes)
>>> b
<itertools.takewhile object at 0x0200F418>
>>> for ele in b:
...     print ele
... 
2
3

itertools.takewhile returns a generator. Looping over generators is faster than looping over lists, but note that generator is exhausted after you loop through it.

Answer 4

Heres the full code:

from math import sqrt

primes = []
for i in range(2, maxvalue):
    for p in primes:
        if p < (1 + int(sqrt(i))) and i % p == 0:
            break
    else:
        primes.append(i)

This is the updated, errorproof function. For maxvalue = 100 it outputs:

[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]

I will note that there may be other, short methods, but I would say this is by far the most human readable