玩蛇网提供最新Python编程技术信息以及Python资源下载!

Python筛法求质数(素数)的生成器示例

python 培训

本篇为大家提供的Python源码是算法相关的:Python筛法求质数(素数)的生成器示例。需要用到math模块的方法。

Python筛法求质数(素数)的生成器的基本思路如下:好比用筛法求素数,用筛法求素数的基本思想是:把从1开始的某一范围内的正整数从小到大顺序排列。因为1不是素数,所以首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推直到筛子为空时结束。

#!/usr/bin/python
# -*- coding: utf-8 -*-

import math

def gen_sieve(ceiling=None):
    if ceiling is not None:
        if ceiling % 2 == 0:
            ceiling -= 1
        highest_prime = math.ceil(math.sqrt(ceiling))

    last_val = 1
    found_primes = []

    yield 2
    while ceiling is None or ceiling > last_val:
        current_val = None

        while current_val is None:
            current_val = last_val = last_val + 2
 
           for prime, square in found_primes:
                if current_val < square: 
                    break
                if current_val % prime == 0:
                    current_val = None
                    break

        yield current_val
 
       if ceiling is None or highest_prime > last_val:
            found_primes.append((current_val, current_val ** 2))

#www.iplaypython.com

def isprime(n):

    for fac in gen_sieve(int(math.ceil(math.sqrt(n)))):
        if n % fac == 0 and n != fac:
            return fac

    return 0

Python素数算法相关文章推荐:Python求素数的快速算法源码示例

玩蛇网原创,转载请注明文章出处和来源网址:http://www.iplaypython.com/code/algorithm/a2596.html



微信公众号搜索"玩蛇网Python之家"加关注,每日最新的Python资讯、图文视频教程可以让你一手全掌握。强烈推荐关注!

微信扫描下图可直接关注

玩蛇网Python新手QQ群,欢迎加入: ① 240764603 玩蛇网Python新手群
文章发布日期:2016-01-08 16:25 玩蛇网 www.iplaypython.com

评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
相关文章推荐
别人正在看
特别推荐
去顶部去底部