title: Python List vs Java Array efficiency
body: <p>I am coming from Java trying to learn Python.  I implmented a <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a> algorithm in Java first, and then in Python.  My Java implementation runs decently fast and I can find all primes under a billion in about 25 seconds.  My Python implementation would probably take about 2 hours to do the same thing.</p>
  
  <p>I have included both implementations here.  My questions are:</p>
  
  <ol>
  <li>why is the Python implmentation so much slower? (I know I am doing something wrong) </li>
  <li>Is it possible for Python to do this as fast as Java?</li>
  </ol>
  
  <p>I assume the slowness centers around using a list in the Python implemenation but I am too new to Python to know how to get around this.</p>
  
  <p>JAVA:</p>
  
  <pre><code>/**
   * Creates a boolean array of a specified size with true values at prime indices and
   * false values at composite indices.
   */
  private static boolean[] sieve(int size){
      boolean[] array = new boolean[size];
  
      //Assume all numbers greater than 1 are prime//
      for(int i = 2; i &lt; array.length; i++){ 
          array[i] = true;
      }
  
      //Execute Sieve of Eratosthenes algorithm//
      for(int p = 2; p &lt; size; p = nextPrimeInArray(array, p)){ 
          for(int i = p + p; i &lt; size; i += p){
              array[i] = false; // i.e., mark as composite
          }
      }
  
      return array;
  }
  
  /**
   * Finds the next index in the array that is not marked composite
   */
  public static int nextPrimeInArray(boolean[] array, int p){
  
      do{
          p++;
      }while(p &lt; array.length &amp;&amp; !array[p]);
      return p;
  }
  </code></pre>
  
  <p>PYTHON:</p>
  
  <pre><code>def getPrimeList(limit):
      """returns a list of True/False values, where list[i] is True if i is prime and False otherwise"""
      primes = []
  
      # Initially assume all numbers in the list are prime
      for i in range(limit):
          primes.append(True)
  
      # Set 0 and 1 to False
      primes[0] = False
      primes[1] = False
  
      for p in range(2, limit):
          for i in range(p + p, limit, p):
              primes[i] = False
          p = nextPrimeInList(primes, p)
      return primes
  
  def nextPrimeInList(list, p):
      """Helper method for getPrimeList that finds the next index in list not marked composite"""
      p += 1
      while p &lt; len(list) and not list[p]:
          p += 1
      return p
  </code></pre>