エラトステネスの篩を頑張って高速化する

prime.py

#!/usr/bin/python
import math

def sieve(n):
    nums = [i+1 for i in range(2, n, 2) if (i+1) % 3 != 0 and (i+1) % 5 !=0]
    ans = [2,3,5]
    while nums[0] <= math.sqrt(n):
        for i in range(nums[0]**2, nums[-1]+1, nums[0]):
            if i in nums: nums.remove(i)
        ans.append(nums.pop(0))
    ans += nums
    return ans

print sieve(10000)