我在Python中使用eratosthenes實現的篩網

Question

您能否看看我在Python中實現eratosthenes篩選並告訴我如何改進/優化它？

我是一名編程初學者，所以我沒有任何想法如何優化它，如果您檢查一下並告訴我哪些可以改進，我將非常感激。

# -*- coding: utf-8 -*- 
""" 
Created on Fri Sep 27 19:57:14 2013 

@author: stefan 
""" 
def sqrt_int(n): 
    n = n**0.5 
    if n == int(n): 
     return True 
    else: 
     return False 

def cbrt_int(n): 
    n = n**(1.0/3) 
    if n == int(n): 
     return True 
    else: 
     return False 

def sieve(limit): 
    first_primes = [2,3,5,7] 
    primes = [x for x in range (2,limit+1)] 

    for y in first_primes: 
     primes = filter(lambda x: x % y != 0, primes) 

    primes = filter(lambda x: not sqrt_int(x), primes) 
    primes = filter(lambda x: not cbrt_int(x), primes) 

    if limit > 10: 
     primes = first_primes + primes 
    else: 
     primes = filter(lambda x: x <= limit, first_primes) 
    return primes 

Answer 1

這裏是埃拉托色尼的篩的更簡單的版本：

def primes(n): # sieve of eratosthenes 
    ps, sieve = [], [True] * (n + 1) 
    for p in range(2, n + 1): 
     if sieve[p]: 
      ps.append(p) 
      for i in range(p * p, n + 1, p): 
       sieve[i] = False 
    return ps 

有辦法使該跑得更快沒有太多的複雜性。如果您對使用素數編程感興趣，我會在我的博客上謙虛地推薦this essay。