Toki
Why so serious?
首页
文章
分类
联系
数据处理 质数筛、快速幂、高精度
质数筛
朴素质数筛
埃氏筛法
欧拉筛法
快速幂
高精度
质数筛
质数:约数只有1和本身,不包含01
质数筛:筛选出0-n全部的质数
朴素质数筛
利用质数特性,一个一个判断
O(n^2)
优化1:大于数的一半的数一定不是数的约数
只需处理n/2及以下的约数。O(n^2)
优化2:假设非质数,则两个因数一个必大于等于根号n,另一个小于等于根号n
只需处理根号n及以下的约数。O(n^(3/2))
埃氏筛法
合数必可被分解为小于它的质数的乘积
似乎是O(nloglogn)
欧拉筛法
每个合数都可以分解为小于它的唯一的质数组合,那么边遍历边筛即可
O(n)
快速幂
利用指数快速增长计算数的幂次
幂的二进制1可视为是否需要乘当前幂次,例如计算2的3次方,3=0b11,即2*4
高精度
大数无法用现有的数据类型精确表示,需要使用数组模拟加减的竖式运算。输入时只能用字符串,结果保存在一个整数数组里
模拟竖式运算的加减乘除
设置一个进位变量会方便很多
2024-09-15
该篇文章被 Toki
归为分类:
数据结构与算法