我在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。