《算法零基础100讲》(第10讲) 因子分解和枚举

举报
英雄哪里出来 发表于 2021/11/28 07:51:30 2021/11/28
【摘要】 因子分解和枚举

零、写在前面

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

一、概念定义

  根据算术基本定理 和 素因子筛选,我们可以对一个数进行素因子的试除,例如:当一个数 n n 存在一个素因子 2 2 的时候,我们可以将它变成 n / 2 n/2 ,然后再判断是否能被 2 2 整除,直到除尽所有 2 2 时,再去判断 3 3 5 5 7 7 等所有 n \sqrt n 内的素因子。
  例如:252 在进行素因子分解后变成 2 2 3 2 7 1 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 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) 1 不需要素因子分解。
  • ( 2 ) (2) primes[0]代表在进行素数筛选时,素数的个数,素数筛选的内容,参考:《算法零基础100讲》(第8讲) 素数筛选
  • ( 3 ) (3) 对每一个素数进行试除;
  • ( 4 ) (4) 调用构造函数;
  • ( 5 ) (5) 如果存在prime[i]这个素因子,则将它除掉,并且个数计数自增;
  • ( 6 ) (6) 记录一个素因子信息;
  • ( 7 ) (7) 所有素数都除不尽,说明它本身是一个素数;

二、题目描述

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

三、算法详解

  首先,枚举 i = n + 1 i=n+1 i = n + 2 i=n+2 两种情况,分别对它们进行 [ 1 , i ] [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 ) (1) 申请一个结果数组;
  • ( 2 ) (2) 枚举 n u m + 1 num+1 n u m + 2 num+2
  • ( 3 ) (3) 不是因子的直接跳过;
  • ( 4 ) (4) 根据因子 i i n / i n/i 的绝对值,取小的记录最优值;
  • ( 5 ) (5) *returnSize作为返回值返回;

五、推荐专栏

💜《夜深人静写算法》💜
三)初等数论入门

六、习题练习

请参考原文

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。