首页

▼ 算法合集

▼ 加密算法

▼ 凯撒密码

凯撒密码

▼ Hill密码算法

Hill密码算法

▼ 多项式哈希算法

多项式哈希算法

▼ Rail Fence Cipher

Rail Fence Cipher

▼ Graph算法

▼ 关节点

关节点

▼ Bellman-Ford算法

Bellman-Ford算法

▼ 广度优先搜索

广度优先搜索

▼ GraphBridges

桥接模式

▼ 深度优先搜索

深度优先搜索

▼ 检测循环

检测循环

▼ Dijkstra算法

Dijkstra算法

▼ Eulerian Path

欧拉路径

▼ Floyd-Warshall算法

Floyd-Warshall算法

▼ HamiltonianCycle

Hamiltonian Cycle

▼ Kruskal算法

Kruskal算法

▼ Prim算法

Prim算法

▼ 强连通分量

强连通分量

▼ 拓扑排序

拓扑排序

▼ Travelling Salesman Problem

Travelling Salesman

▼ 图像处理算法

▼ Seam Carving算法

内容感知缩放算法

▼ 链表

▼ 反向遍历

反向遍历

▼ GraphTraversal

GraphTraversal

▼ 数学算法

▼ 二进制浮点数

BinaryFloatingPoint

▼ 位操作

位操作算法

▼ 复数

复数

▼ 欧几里得算法

Euclidean Algorithm

▼ Euclidean Distance

欧几里得距离

▼ 阶乘算法

阶乘算法

▼ 快速幂算法

快速幂算法

▼ Fibonacci数列

斐波那契数列

▼ 傅里叶变换

Fourier变换

▼ Horner法

霍纳法则

▼ 整数划分

整数划分

▼ 判断是否为2的幂

判断是否为2的幂

▼ 最小公倍数

最小公倍数

▼ Liu Hui

Liu Hui

▼ 矩阵

Matrix

▼ Pascal三角形

Pascal三角形

▼ Primality Test

素数测试

▼ 质因数

质因数

▼ 弧度计算

弧度计算

▼ 埃拉托色尼筛法

埃拉托色尼筛法

▼ SquareRoot

SquareRoot

▼ MachineLearning

▼ K均值算法

K均值算法

▼ K近邻算法

K近邻算法

▼ 搜索算法

▼ 二分查找算法

二分查找

▼ 插值搜索算法

插值搜索算法

▼ 跳跃搜索算法

跳跃搜索算法

▼ 线性搜索

线性搜索算法

▼ 集合

▼ 笛卡尔积

笛卡尔积

▼ 组合总和

组合总和

▼ 组合算法

组合算法

▼ Fisher-Yates洗牌算法

Fisher-Yates洗牌算法

▼ 背包问题

背包问题

▼ 最长公共子序列

最长公共子序列

▼ 最长递增子序列

最长递增子序列

▼ 最大子数组

最大子数组

▼ 排列组合

排列组合

▼ 幂集

幂集算法

▼ 最短公共超序列

最短公共超序列

▼ Sorting Algorithms

▼ 冒泡排序

冒泡排序

▼ 桶排序算法

桶排序算法

▼ 计数排序算法

计数排序

▼ 堆排序算法

堆排序

▼ 插入排序

插入排序

▼ 归并排序

归并排序

▼ 快速排序算法

快速排序算法

▼ 基数排序

基数排序

▼ 选择排序算法

选择排序算法

▼ 希尔排序

希尔排序

▼ 统计学

▼ 加权随机

加权随机算法

▼ 字符串算法

▼ Hamming距离

Hamming距离

▼ KnuthMorrisPratt算法

Knuth-Morris-Pratt算法

▼ LevenshteinDistance

Levenshtein距离

▼ 最长公共子串

最长公共子串

▼ 回文检测算法

回文检测算法

▼ Rabin-Karp算法

Rabin-Karp算法

▼ 正则表达式匹配

正则表达式匹配

▼ Z算法

Z算法

▼ Tree Data Structure

▼ 广度优先搜索

广度优先搜索

▼ 深度优先搜索

深度优先搜索

▼ 未分类

▼ 最佳买卖股票时机

最佳买卖股票时机

▼ 汉诺塔算法

HanoiTower

▼ 跳跃游戏算法

跳跃游戏

▼ KnightTour

骑士巡逻

▼ N皇后问题

N皇后问题

▼ 雨水收集

雨水收集

▼ 递归楼梯问题

递归楼梯问题

▼ 方阵旋转

方阵旋转

▼ 独特路径

UniquePaths

▼ 数据结构

▼ BloomFilter算法

布隆过滤器

▼ 不相交集数据结构

Disjoint Set

▼ 双向链表

双向链表

▼ Graph

Graph算法

▼ 哈希表

哈希表

▼ Heap数据结构

Heap数据结构

▼ 链表

链表

▼ LRU缓存

LRU缓存

▼ 优先队列

优先队列

▼ 队列

队列

▼ 栈结构

栈结构

▼ Tree Data Structure

树结构

▼ AVL树

AVL树

▼ 二叉搜索树

二叉搜索树

▼ Fenwick树

Fenwick树

▼ 红黑树

红黑树

▼ 线段树

SegmentTree

▼ Trie数据结构

Trie数据结构

质数因子

Read this in other languages: english.

质数 是一个比 1 大的整数,且 不能由其它整数相乘得出。前几个质数是: 2, 3, 5, 7, 11, 13, 17, 19,依此类推。

如果我们通过其它整数相乘得出,我们则称它为合数

Composite numbers

Image source: Math is Fun

质数因子是那些相乘得到原始数的质数。例如39的质数因子是31315的质数因子是35

Factors

Image source: Math is Fun

正确计算所有的质数因子及其数量

这个方法将自然数ni = 2除到i = n(仅按质数索引)。且每次循环后n的值被(n / i)的值替换。

在最坏的情况下,即循环从i = 2执行到 i = n,上述方法的时间复杂度为O(n)。时间复杂度其实可以从O(n)减少到O(sqrt(n)),通过减少循环的执行次数,从i = 2执行到 i = sqrt(n)。因为可以确认,当i大于sqrt(n)时,除了n本身,再没有数可以被整除了。

Hardy-Ramanujan公式用于计算质数因子的个数

1917年,G.H Hardy和Srinivasa Ramanujan提出了一个定理,该定理指出,自然数 n 的不同素数的数 ω(n) 的正态次序是log(log(n))

粗略地讲,这意味着大多数数字具有这个数量的质数因子。

References