试除法判断质数、分解质因数
c++/* * 试除法判断质数、分解质因数 * 本次将要介绍关于质数两个比较常见的算法，试除法判断质数和分解质因数 * * 质数定义: * 质数，又叫素数，是指一个大于1的自然数，且除了1和它本身外，不能被其他自然数整除的数。换句话说，就是该数除了1 和它本身以外，不再有其他的因数。 * * 算法 1. 试除法判断质数: * 算法流程: * 试除法判断质数是从质数的定义出发，对待判断的数字 x 而言，从 2 -> x - 1，判断是否可以被整除。 O(N) 复杂度。 * 但是考虑到倘若 x 存在因数 a, 那么 b = x / t， b 也是 x 的因数，并且 x = a * b。假设 a != 1 && a != x， * 那么 a, b 中至少存在一个数字
页:
[1]