title: Python: speed up removal of every n-th element from list
body: <p>I'm trying to solve <a href="http://www.spoj.pl/problems/ASSIST/" rel="nofollow noreferrer">this programming riddle</a> and although the solution (see code below) <strong>works</strong> correctly, it is too slow for succesful submission.</p>
  
  <ul>
  <li>Any pointers as how to make this run
  faster (removal of every n-th element from a list)?</li>
  <li>Or suggestions for a better algorithm to calculate the same; seems I can't think of anything
  else than brute-force for now...</li>
  </ul>
  
  <p>Basically, the task at hand is:</p>
  
  <pre>
  GIVEN:
  L = [2,3,4,5,6,7,8,9,10,11,........]
  1. Take the first remaining item in list L (in the general case 'n'). Move it to 
     the 'lucky number list'. Then drop every 'n-th' item from the list.
  2. Repeat 1
  
  TASK:
  Calculate the n-th number from the 'lucky number list' ( 1 &lt;= n &lt;= 3000)
  </pre>
  
  <p>My original code (it calculated the 3000 first lucky numbers in about a second on my machine - unfortunately too slow):</p>
  
  <pre><code>"""
  SPOJ Problem Set (classical) 1798. Assistance Required
  URL: http://www.spoj.pl/problems/ASSIST/
  """
  
  sieve = range(3, 33900, 2)
  luckynumbers = [2]
  
  while True:
      wanted_n = input()
      if wanted_n == 0:
          break
  
      while len(luckynumbers) &lt; wanted_n:
          item = sieve[0]
          luckynumbers.append(item)
          items_to_delete = set(sieve[::item])
          sieve = filter(lambda x: x not in items_to_delete, sieve)
      print luckynumbers[wanted_n-1]
  </code></pre>
  
  <p><strong>EDIT: thanks to</strong> the terrific contributions of Mark Dickinson, Steve Jessop and gnibbler, I got at the following, which is quite a whole lot faster than my original code (and succesfully got submitted at <a href="http://www.spoj.pl" rel="nofollow noreferrer">http://www.spoj.pl</a> with 0.58 seconds!)...</p>
  
  <pre><code>sieve = range(3, 33810, 2)
  luckynumbers = [2]
  
  while len(luckynumbers) &lt; 3000:
      if len(sieve) &lt; sieve[0]:
          luckynumbers.extend(sieve)
          break
      luckynumbers.append(sieve[0])
      del sieve[::sieve[0]]
  
  while True:
      wanted_n = input()
      if wanted_n == 0:
          break
      else:
          print luckynumbers[wanted_n-1]
  </code></pre>