python - Speeding up string splitting and concatenation -

i'm trying solve project euler's problem #35

the number, 197, called circular prime because rotations of digits: 197, 971, , 719, prime.

how many circular primes there below 1 million?

this solution:

import numpy np  def problem(n=100):      circulars = np.array([], np.int32)      p = np.array(sieveofatkin(n), np.int32)     prime in p:         prime_str = str(prime)         is_circular = true         in xrange(len(prime_str)):             m = int(prime_str[i:]+prime_str[:i])             if not m in p:                 is_circular = false          if is_circular:             circulars = np.append(circulars, [prime])      return len(circulars) 

unfortunately for-loop mighty slow! ideas how can speed up? suspect string concatenation bottleneck, not entirely sure! :)

---

any ideas? :)

1. use set membership testing instead of array. hash lookup o(1) instead of o(n). biggest bottleneck.

2. break out of loop see it's not circular prime instead of trying other rotations. bottleneck.

---

here, i've isolated circularity testing function allow list built list comprehension. having in function, lets return false know it's not circular. alternative in for loop , break when know it's not circular. append list in loop's else clause. speaking, list comps faster appending in loop though. might not case here because add function call overhead. if care speed, worth profile both options.

primes = set(primes_to_one_million_however_you_want_to_get_them)  def is_circular(prime, primes=primes):    prime_str = str(prime)    # sven marnach's comments    return all(int(prime_str[i:]+prime_str[:i]) in primes                in xrange(len(prime_str)))   circular_primes = [p p in primes if is_circular(p)] 

i've used trick of passing global default argument is_circular function. means can accessed within function local variable instead of global variable faster.

here's 1 way code using else clause on loop rid of ugly flag , improve efficiency.

circular = [] p in primes:    prime_str = str(prime)    in xrange(len(prime_str)):        if int(prime_str[i:]+prime_str[:i]) not in primes:             break    else:        circular.append(p)