国外搜索引擎网站,辽宁建设工程信息网新平台,太原网络推广公司,网站建设公司找哪家好1 判断一个数是不是质数(素数) 方法1#xff1a;依次判断能否被n整除即可#xff0c;能够整除则不是质数#xff0c;否则是质数 方法2#xff1a;假如n是合数#xff0c;必然存在非1的两个约数p1和p2#xff0c;其中p1sqrt(n)#xff0c;p2sqrt(n)。 方法3…1 判断一个数是不是质数(素数) 方法1依次判断能否被n整除即可能够整除则不是质数否则是质数 方法2假如n是合数必然存在非1的两个约数p1和p2其中p1sqrt(n)p2sqrt(n)。 方法3等于 6x-1 或者 6x1其中 x 是大于等于1的自然数。 2 判断一段素数
2.1 Eratosthenes 筛法 O(Nlog(logN)) Eratosthenes 筛法进行的是打表也就是平时说的离线操作当查询量比较大的时候我们往往采用这种方法进行离线操作处理该算法的内容是首先假设 n 个数全部都是素数然后从 2 开始把每一个数的倍数都剔除并标记成合数因为合数肯定是有素因子的这样列表中保存着的都是没有素因子的数就是我们想要的质数了。 n max(2, n) #处理输入数字为0的情况
is_prime n * [1] #标记是不是素数
is_prime[0] is_prime[1] 0for i in range(2, n): # 从2开始if is_prime[i]: #如果不是素数for j in range(2, n): # 就标记他的倍数的数字剔除素数队列if i * j n: breakis_prime[i * j] 0
return sum(is_prime)比如对数字 6 来说素因子 2 和 3 在筛选过程中都对他进行了剔除标记也就是说所有 6 的倍数至少都被 2 和 3 进行了重复的剔除。 Eratosthenes 筛法的时间复杂度理论值是 O(Nlog(logN)) 2.2 欧拉筛法 - 线性筛 O(N) 我们只对小于等于 sqrt(n) 的数进行取余检查这里可以采取类似但是更简洁的办法只要保证每个合数只会被他的最小素因子筛掉就可以了所以我们优化算法的核心 寻找并保存当前的素数 对每个数的从小到大的素数次倍数进行标记当发现这个数的素因子后停止这也就保证每个数都是被最小素因子筛掉的 线性筛的理论复杂度是 O(N) n max(2, n)
primes n * [0] # 保存已经筛出的素数
cnt 0 # 记录已经筛出的素数个数
is_prime n * [1]
is_prime[0] is_prime[1] 0
for i in range(2, n):if is_prime[i]: # 保存已经筛出的素数primes[cnt] icnt 1for j in range(cnt):# 如越界则停止if primes[j] * i n: break # 标记 i 的素数次倍数is_prime[primes[j] * i] 0# 如遇到 i 的素因数则停止#这句代码保证了每个数最多被筛一次将时间复杂度降到了线性。证明如下if i % primes[j] 0: break
return sum(is_prime)注意到筛法求素数的同时也得到了每个数的最小质因子。 2.3 meissel–lehmer亚线性时间找出素数个数 证明与推理过程
2.4 杜教筛洲阁筛
3 根据筛法求【筛法可得到最小质因子】
3.1 筛法求欧拉函数
欧拉函数是小于等于n的正整数中与n互质的数的数目
3.2 筛法求莫比乌斯函数 莫比乌斯函数由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)miu(n)作为莫比乌斯函数的记号。据说高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数。 具体定义如下 如果一个数包含平方因子那么miu(n) 0。例如miu(4), miu(12), miu(18) 0。 如果一个数不包含平方因子并且有k个不同的质因子那么miu(n) (-1)^k。例如miu(2), miu(3), miu(30) -1,miu(1), miu(6), miu(10) 1。 给出一个数n, 计算miu(n)。 3.3 筛法求约数个数
3.4 筛法求约数和
4 最大公约数Greatest Common Divisor GCD
4.1 欧几里得算法 求 GCD 在数论中公认的最常用算法即为欧几里得算法也就是我们在高中时学到的辗转相除法。 欧几里得算法的基本原理用一句话就可以说清楚两个整数的最大公约数等于其中较小的数和两数的差的最大公约数gcd(a,b)gcd(b,a mod b) 。 4.2 扩展欧几里得算法 丢番图方程Diophantine Equation 丢番图方程指的是未知数个数多于方程个数且未知数只能是整数的整数系数方程或方程组。 例如以下式中 a,b,c 都为整数: a1*x1b1 a2*x2b2 …… an*xnbn n 裴蜀定理Bézout’s identity 在数论中裴蜀定理是一个关于最大公约数的定理。这个定理说明了对于任意整数 a、b 和他们的最大公约数 d关于未知数 x 和 y 的线性丢番图方程axbym有解当且仅当 m 是 d 的倍数时。这个等式也被称为裴蜀等式。 裴蜀等式有解时必然有无穷多个整数解每组解 x 、y 都称之为裴蜀数可用辗转相除法求得。 辗转相除法实现扩展欧几里得算法 既然说可以用辗转相除法来解决这个问题那么我们先来说明一下如何通过辗转相除法来求二元一次线性丢番图方程。 辗转相除法过程 以 23x 17y 1 为例我们来求 GCD(23, 17) 23 17 * 1 6 17 6 * 2 5 6 5 * 1 1 5 1 * 5 0 1 0 * 0 1 改写成余数形式 将等式右边的第一项移项 23×117×−16 (1) 17×16×−25 (2) 6×15×−11 (3) 反向带入原式 带下划线的 6 和 5 会使用 (1) 和 (2) 两个式子反向带入形同换元 16 ×1 5 ×(-1) (1)×1(2)×−1 (23×117×−1)[17×1(23×117×−1)×−2]×−1 23×317×−4 23x17y 所以反解得x 3, y -4 是上述二元一次线性丢番图方程的一组解。 扩展欧几里得算法证明
5 根据最大公约数求
5.1 根据两个杯子得到指定target的水
5.2 根据两个电容得到指定target的电量 情况一 边界情况即当 cmax(a,b) 这种情况是无法使得 A 和 B 的电量达到 c 的。直接输出 0。 情况二 当 a c 或者 b c 的时候只进行一次充电操作就可以完成直接输出 1。 情况三 接下来我们考虑一般情况即需要满足以下前提条件 cmax(a,b)且 c不等于min(a,b) 我们将这个问题换一个思路转化一下假设给出的 a 、b、 c 一定有解那么我们来设置对 A 做了 x 次的充放电对 B 做了 y 次的充放电并且做了 k 次的操作三。 如果将 A、B 当做一个大电容来看这个电容只有充放电 a 单位、充放电 b 单位这 4 种操作。那么我们就可以列出一个关系式 axbyc由于 a、b 为非负整数又因为前提条件则 x 和 y 符号相反。 暂且我们先不管做了几次操作三先只考虑充放电问题那其实就是已知 a、b、c我们在给定范围内求解 x 和 y 的解就可以了。那么这个问题我们要如何求解呢这就是扩展欧几里得算法所要解决的问题。 axbygcd(a,b)×kc def ex_gcd(a, b):if b 0:return 1, 0, aelse:x, y, r ex_gcd(b, a % b) x, y y, (x - (a // b) * y)return x, y, r
