关于质数(素数)

栏目: Python · 发布时间: 5个月前

来源: juejin.im

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

质数(Prime number)又称素数, 质数是大于 而且只能被 和自身整除的自然数。大于 的自然数如果不是素数,就称为合数(Composite number)。

算术基本定理

算术基本定理最早由欧几里得证明, 是表示任何合数都可以不断分解成素数的组合,如 可以分解为 两个素数,欧几里得发现把这些素数因子的次方相乘可以得到原来的数字 ,而且这种分解为素数乘积的方式是唯一的。素数因子分解就像是一个锁,而且只有一把开锁的钥匙,这也是现代密码学的基础。

素数定理

素数定理描述素数在自然数中分布的渐进情况,就是小于 中素数的个数随着 的增大素数的密度就越来越小。当 越来越大时它的图像就越来越接近 。所以一个数字内素数的数量 约等于

试除法

那么怎么判断一个数是不是素数?这也是很多面试题里面问到的。一种简单的方法是试除法。

比如判断 是不是素数,可以让 除以 到 之间的整数,如果可以除尽则表示是合数否则是质数。

def isPrime(n):
    if n < 2: return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
复制代码

但是可以发现大于 偶数都不是质数,因为它们可以被 整除,所以这可以减少迭代次数。

def isPrime(n):
    if n == 2: return True
    if n < 2 or n % 2 == 0: return False
    for i in range(3,n,2):
        if n % i == 0:
            return False
    return True
复制代码

还有没有更快的方法?有,就是迭代到 ,因为一个数字分解为两个因子,其中必然有一个小于或等于 ,不然两个都大于 它们相乘就大于 了。

def isPrime(n):
    if n == 2: return True
    if n < 2 or n % 2 == 0: return False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True
复制代码

试除法还能不能更快?根据算术基本定理任何合数最终都可以分解为素数的组合,所以只用除小于 的素数就行了。

筛选法

筛选法可以给出小于 的素数序列,比如要生成 内的素数序列,首先可以生成2到100间数字表,然后将列表第一个没被标记的数字标记为素数然后将数字表中它的倍数标记为合数,然后不断重复这个步骤。

关于质数(素数)
def genPrimes():
    primes = [2]
    i = 1
    yield 2
    while True:
        i += 2
        for p in primes:
            if i % p == 0:
                break
        else:
            primes.append(i)
            yield i
复制代码

费马小定理

虽然一般判断是不是素数用 试除法 就行了,但是当要判断一个大数是不是素数时,也还是太慢了。

费马小定理 是欧拉定理的一个特殊情况,它是说一个正整数 的 质数 次方减 可以被 次方整除。用公式表示可以为 。

但是也不能完全正确,比如 但是 ,所以可以随机生成多个 来测试,这样就可以降低将出错概率。

import random
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def randA(p):
    return random.randint(1, p - 1)
def fastMod(f, p, m):
    ans = 1
    whlie p > 0:
        if p % 2 == 1:
            ans = (ans * f) % m
            p -= 1
        p //= 2
        f = (f ** 2) % m
    return ans
def isPrime(p):
    trials = 30
    for i in range(trials):
        a = randA(p)
        if gcd(a, p) != 1: return False
        if fastMod(a, p - 1, p) != 1: return False
    return True
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

为你推荐:

相关软件推荐:

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

素数之恋

素数之恋

(美)约翰·德比希尔 / 陈为蓬 / 上海科技教育出版社 / 2008-12-01 / 34.00元

1859年8月,没什么名气的32岁数学家黎曼向柏林科学院提交了一篇论文,题为“论小于一个给定值的素数的个数”。在这篇论文的中间部分,黎曼作了一个附带的备注——一个猜测,一个假设。他向那天被召集来审查论文的数学家们抛出的这个问题,结果在随后的年代里给无数的学者产生了近乎残酷的压力。时至今日,在经历了150年的认真研究和极力探索后,这个问题仍然悬而未决。这个假设成立还是不成立? 已经越来越清楚,......一起来看看 《素数之恋》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具