零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第十天了，虽然打卡人数看起来越来越少，但是 第一天打卡刷题 的人数与日俱增，源源不断的新生代涌入 万人千题 计划，目前已破千人，成功的路上永远不会孤独，与神同行，坚持下去，爆发只在一瞬之间。

一、概念定义

  根据算术基本定理 和 素因子筛选，我们可以对一个数进行素因子的试除，例如：当一个数 $n$ 存在一个素因子 $2$ 的时候，我们可以将它变成 $n/2$，然后再判断是否能被 $2$ 整除，直到除尽所有 $2$ 时，再去判断 $3$、 $5$、 $7$ 等所有 $\sqrt n$ 内的素因子。
  例如：252 在进行素因子分解后变成 $2^2 3^2 7^1$ 。
  首先准备一个结构体factor，用来表示它的素因子是什么，以及该素因子的个数。

struct factor {
	int prime, count;
	factor() :prime(0), count(0) {}
	factor(int p, int c) : prime(p), count(c) {}
	void print() {
		printf("(%d, %d)\n", prime, count);
	}
};

  然后，利用一个素因子分解的接口Factorization(int n, vector <factor>& ans)来实现枚举素因子的分解。即对于 $n=252$ 的情况，函数计算完毕后，ans中存的结果是：[ (2,2), (3,2), (7,1) ]

void Factorization(int n, vector <factor>& ans) {
	ans.clear();
	if(n == 1) {
		return ;                           // (1)
	}
	// 素数试除 
	for(int i = 1; i <= primes[0]; i++) {  // (2)
		if(n % primes[i] == 0) {           // (3)
			factor f(primes[i], 0);        // (4)
			while( !(n % primes[i]) ) {    // (5)
				n /= primes[i];
				f.count ++;            
			}
			ans.push_back(f);              // (6)
		}
		if(n == 1) {
			return ;
		}
	}
	ans.push_back( factor(n, 1) );        // (7)
}

• $(1)$ 1 不需要素因子分解。
• $(2)$ primes[0]代表在进行素数筛选时，素数的个数，素数筛选的内容，参考：《算法零基础100讲》(第8讲) 素数筛选。
• $(3)$ 对每一个素数进行试除；
• $(4)$ 调用构造函数；
• $(5)$ 如果存在prime[i]这个素因子，则将它除掉，并且个数计数自增；
• $(6)$ 记录一个素因子信息；
• $(7)$ 所有素数都除不尽，说明它本身是一个素数；

二、题目描述

  给定一个整数 $n(n \le 10^9)$，请找出同时满足下面全部要求的两个整数：
    1）两数乘积等于 $n + 1$ 或 $n + 2$；
    2）以绝对差进行度量，两数大小最接近；

三、算法详解

  首先，枚举 $i=n+1$ 和 $i=n+2$ 两种情况，分别对它们进行 $[1, \sqrt i]$ 的试除，计算绝对值，去绝对值小的整数对计入答案。

四、源码剖析

int* closestDivisors(int num, int* returnSize){
    int *ret = (int *)malloc( 2 * sizeof(int) );        // (1)
    int n, i, sub = -1;
    for (n = num+1; n <= num+2; ++n) {                  // (2)
        for(i = 1; i * i <= n; ++i) {
            if(n % i)                                   // (3)
                continue;
            if ( sub == -1 || abs(n/i - i) < sub ) {    // (4)
                sub = abs(n/i - i);
                ret[0] = n/i;
                ret[1] = i;
            }
        }
    }
    *returnSize = 2;                                    // (5)
    return ret;
}

• $(1)$ 申请一个结果数组；
• $(2)$ 枚举 $num+1$ 和 $num+2$；
• $(3)$ 不是因子的直接跳过；
• $(4)$ 根据因子 $i$ 和 $n/i$ 的绝对值，取小的记录最优值；
• $(5)$ *returnSize作为返回值返回；

五、推荐专栏

六、习题练习

请参考原文