当前位置:网站首页>【第29天】给定一个整数,请你求出它的因子数
【第29天】给定一个整数,请你求出它的因子数
2022-07-03 00:51:00 【执 梗】
序、专栏前言
本专栏开启,目的在于帮助大家更好的掌握学习Java
,特别是一些Java学习者
难以在网上找到系统地算法学习资料帮助自身入门算法,同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
但最最主要的还是需要独立思考,对于本专栏的所有内容,能够进行完全掌握,自己完完全全将代码写过一遍,对于算法入门肯定是没有问题的。
算法的学习肯定不能缺少总结,这里我推荐大家可以到高校算法社区将学过的知识进行打卡,以此来进行巩固以及复习。
学好算法的唯一途径那一定是题海战略,大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。
一、【例题1】
1、题目描述
给定一个整数 n ( 1 ≤ n ≤ 100000 ) n(1\le n \le100000) n(1≤n≤100000),请你求出它的因子数量。
2、解题思路
- ( 1 ) (1) (1)我们可以联想到之前判断质数的文章,因为质数的判定也是看一个数的因子数,那时就已经写出了 O ( n ) O(n) O(n)和一个 O ( n ) O(\sqrt n) O(n)的做法。
3、模板代码
1.O(n)做法
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int ans=0;
for (int i = 1; i <=n; i++) {
if (n%i==0) ans++;
}
System.out.println(ans);
}
}
2.根号n做法
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int ans=0;
for (int i = 1; i <=n/i; i++) {
if (n%i==0){
if (i!=n/i) ans+=2;
else ans++;
}
}
System.out.println(ans);
}
}
3.约数个数定理
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(getsum(n));
}
static int getsum(int n){
int ans=1;
for (int i = 2; i <=n/i; i++) {
if (n%i==0){
int a=0;
while (n%i==0){
a++;
n/=i;
}
ans*=(a+1);
}
}
if (n>1) ans*=2;
return ans;
}
}
4、代码解析
- ( 1 ) (1) (1)前两种方法在这不讲,在第 5 5 5天的质数判定中讲解过,重点讲一下约数个数定理。
- ( 2 ) (2) (2)对于一个大于 1 1 1的整数 n n n,可以分解质因数
n = ∏ i = 1 k p i a i = p 1 a 1 × p 2 a 2 × p 3 a 3 . . . . . . p k a k n=\prod_{i=1}^{k} p_i^{a^i}=p_1^{a^1}\times p_2^{a^2}\times p_3^{a^3}......p_k^{a^k} n=i=1∏kpiai=p1a1×p2a2×p3a3......pkak
则 n n n的正约数个数为 f ( n ) = ∏ i = 1 k ( a i + 1 ) = ( a 1 + 1 ) ( a 2 + 1 ) . . . ( a k + 1 ) 。 f(n)=\prod_{i=1}^{k}(a_i+1)=(a_1+1)(a_2+1)...(a_k+1)。 f(n)=∏i=1k(ai+1)=(a1+1)(a2+1)...(ak+1)。
其中 a 1 、 a 2 、 a 3 . . . a k a_1、a_2、a_3...a_k a1、a2、a3...ak是 p 1 、 p 2 、 p 3 、 . . . p k p_1、p_2、p_3、...p_k p1、p2、p3、...pk的指数。 - ( 3 ) (3) (3)定理证明:对于 n n n,我们有: n = p 1 a 1 × p 2 a 2 × p 3 a 3 . . . . . . p k a k n=p_1^{a^1}\times p_2^{a^2}\times p_3^{a^3}......p_k^{a^k} n=p1a1×p2a2×p3a3......pkak
对于 n n n的任意一个约数 d d d,则有 d = p 1 β 1 × p 2 β 2 × p 3 β 3 . . . . . . p k β k d=p_1^{^\beta1}\times p_2^{\beta ^2}\times p_3^{\beta ^3}......p_k^{\beta^k} d=p1β1×p2β2×p3β3......pkβk,其中 ( 0 ≤ β i ≤ a i ) (0 \le \beta_i \leq a_i) (0≤βi≤ai),每一个 β i \beta_i βi的取值总共有 ( a i + 1 ) 个 (a_i+1)个 (ai+1)个。每一项的 β i \beta _i βi不同,则约数就不相同。 β 1 \beta _1 β1的范围是 [ 0 , a 1 ] [0,a_1] [0,a1], β 2 \beta _2 β2的范围是 [ 0 , a i ] [0,a_i] [0,ai], β k \beta _k βk的去取值范围是 [ 0 , a k ] [0,a_k] [0,ak]。 - ( 4 ) (4) (4)根据乘法原理, n n n的约数个数 f ( n ) = ( a 1 + 1 ) ( a 2 + 1 ) . . . ( a k + 1 ) f(n)=(a_1+1)(a_2+1)...(a_k+1) f(n)=(a1+1)(a2+1)...(ak+1)
三、推荐专栏
四、课后习题
序号 | 题目链接 | 难度评级 |
---|---|---|
1 | 丑数 | 2 |
边栏推荐
- Leetcode-934: the shortest Bridge
- 【FPGA教程案例6】基于vivado核的双口RAM设计与实现
- ROS2之ESP32简单速度消息测试(极限频率)
- Leetcode-2115: find all the dishes that can be made from the given raw materials
- Key wizard hit strange learning - automatic path finding back to hit strange points
- excel IF公式判断两列是否相同
- [AUTOSAR five methodology]
- kivy教程之在 Kivy App 中使用 matplotlib 的示例
- 【C语言】分支和循环语句(上)
- 解决ReactNative使用webView存在缓存问题
猜你喜欢
[AUTOSAR twelve mode management]
Cut point of undirected graph
leetcode:871. Minimum refueling times [Pat has done before + maximum stacking + greed]
合并K个已排序的链表
瑞萨电子RZ/G2L开发板上手评测
[AUTOSAR nine c/s principle Architecture]
MySQL basic usage 02
[introduction to AUTOSAR seven tool chain]
Excel calculates the difference between time and date and converts it into minutes
RISA rz/g2l processor introduction | frame diagram | power consumption | schematic diagram and hardware design guide
随机推荐
18_微信小程序之微信视频号滚动自动播放视频效果实现2.0
瑞萨RZ/G2L 处理器简介|框架图|功耗|原理图及硬件设计指南
Cut point of undirected graph
MySQL multi table joint deletion
Linear programming of mathematical modeling (including Matlab code)
First hand evaluation of Reza electronics rz/g2l development board
无向图的割点
比较版本号
Correctly distinguish the similarities and differences among API, rest API, restful API and web service
[AUTOSAR XIII NVM]
按键精灵打怪学习-回城买药加血
Leetcode-2115: find all the dishes that can be made from the given raw materials
R language uses coin package to apply permutation tests to independence problems (permutation tests, whether response variables are independent of groups, are two numerical variables independent, and
递归处理组织的几种情况
excel去除小数点后面的数据,将数字取整
[AUTOSAR I overview]
12_微信小程序之微信视频号滚动自动播放视频效果实现
Leetcode-2280: represents the minimum number of line segments of a line graph
这不平凡的两年,感谢我们一直在一起!
JS inheritance and prototype chain