- 浏览: 21244 次
- 性别:
- 来自: 南京
最新评论
求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这20个数的最小公倍数。
求n个数的最小公倍数,以a,b,c三个数为例,他们的最小公倍数等于:先求a与b的最小公倍数m,然后m和c的最小公倍数即着三个数的最小公倍数。
求两个数a,b的最小公倍数嘛,先取出其中较大的那个比如a,然后再用k*a去试探能否被较小那个数整除,其中,k是从1开始的自然数 k*a<a*b。
int get_lcm(int a, int b)
{
if(a==b)
{
return a;
}
int bigger = a<b?b:a;
int smaller= a<b?a:b;
int max = a*b;
int i;
for(i=bigger; i<max; i+=bigger)
{
if(i%smaller == 0)
{
return i;
}
}
return max;
}
另外一种比较好的方法,以n取10为例
2,3,4,5,6,7,8,9,10 (1没有什么意义,忽略掉了)
将这些数字分解质因数:
2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5
这些质数分别是2, 3, 5, 7
最终答案可以表示为:
2^a * 3^b * 5^c * 7^d (其中,x^y表示x的y次方)
其中的英文字母表示在上面分解质因数时所得到的表达式中质因数在同一个表达式中出现的次数的最大值。
质因数2出现次数最多是在8=2*2*2中,其出现了3次,所以a为3。
同理可得到:2^3 * 3^2 * 5^1 * 7^1 = 2520。
求n个数的最小公倍数,以a,b,c三个数为例,他们的最小公倍数等于:先求a与b的最小公倍数m,然后m和c的最小公倍数即着三个数的最小公倍数。
求两个数a,b的最小公倍数嘛,先取出其中较大的那个比如a,然后再用k*a去试探能否被较小那个数整除,其中,k是从1开始的自然数 k*a<a*b。
int get_lcm(int a, int b)
{
if(a==b)
{
return a;
}
int bigger = a<b?b:a;
int smaller= a<b?a:b;
int max = a*b;
int i;
for(i=bigger; i<max; i+=bigger)
{
if(i%smaller == 0)
{
return i;
}
}
return max;
}
另外一种比较好的方法,以n取10为例
2,3,4,5,6,7,8,9,10 (1没有什么意义,忽略掉了)
将这些数字分解质因数:
2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5
这些质数分别是2, 3, 5, 7
最终答案可以表示为:
2^a * 3^b * 5^c * 7^d (其中,x^y表示x的y次方)
其中的英文字母表示在上面分解质因数时所得到的表达式中质因数在同一个表达式中出现的次数的最大值。
质因数2出现次数最多是在8=2*2*2中,其出现了3次,所以a为3。
同理可得到:2^3 * 3^2 * 5^1 * 7^1 = 2520。
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 661最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1058在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 890排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 720题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1293题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 574给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 939在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 710乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 755最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
2520是最小的能被1-10中每个数字整除的正整数。 最小的能被1-20中每个数整除的正整数是多少? 保证运行出结果
输入数据保证a0 能被a1 整除,b1 能被b0 整除。 输出: 共一行,对于输入的数据:若不存在这样的x,请输出0;若存在这样的 x,请输出满足条件的x 的个数。 输入样例: 41 1 96 288 输出样例: 6
Hanks博士是BT ( Bio-Tech,生物技术)领域的知名专家,他的...输入数据保证a0能被a1整除,b1能被b0整除。 输出格式: 输出共n行。每组输入数据的输出结果占一行,为一个整数。 对于每组数据:若不存在这样的x,请输出0;
二、输入两个正整数m、n,完成如下功能:(根据题目要求调用上述功能函数)(1)求出m和n两个数之间所有“明7暗7”数,即数字中有7或能整除7,如37,63.(2)分别求出m! 和 n!(3)求m和n的最大公约数和最小公倍数。...
将一个正整数分解质因数。例如:输入90,打印出90=2*3...(2)如果n>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步。 (3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。 */
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
FILL从键盘输入一个数字组成的字符串将字符串转换成十进制数.CFILL二维...1到M之间的奇数之和和偶数之和.CFILL求cmn.CFILL求fabonacci数列前20项的值.CFILL求m和n之间既能被3又能被7整除的整数的和.CFILL求M行N列的二...
关于信息学奥赛一本通网站上的1154题:亲和数:自然数a的因子是指能整除a的所有自然数,但不含a本身。例如12的因子为:1,2,3,4,6。若自然数a的因子之和为b,而且b的因子之和又等于a,则称a,b为一对“亲和数” 。求...
在大于1的整数中,除了1和该数自身外,无法被其他整数整除的数。大于1的数若不为素数,则被称为合数,也叫作合成数。 素数的特点 大于2的质数只能是奇数。(不能说大于2的奇数都是质数。) 大于5的质数,个位数只能是1...
1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
例如,对于整数4和6,它们的最小公倍数是12,因为12是4和6都能整除的最小正整数。求最小公倍数在分数加减、解同余方程、规划问题等方面都有重要应用。 要求两个数的最小公倍数,最常用的方法是先找到这两个数的最大...
(2)如果n <> k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你,重复执行第一步。 (3)如果n不能被k整除,则用k 1作为k的值,重复执行第一步。 后附有本示例完整的源代码下载,请参考。
# 题目: # 将一个正整数分解质因数。...# (2) 如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步。 # (3) 如果n不能被k整除,则用k+1作为k的值,重复执行第一步。
最小公倍数(Least Common Multiple,简称LCM)则是指能被两个或多个整数共同整除的最小正整数。例如,对于整数12和18,它们的最小公倍数是36。 求解最大公约数和最小公倍数的方法有很多种,如质因数分解法、短除法...
程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序15】 题目:打印出如下图案(菱形) * *** ****** ******** ****** *** * ...
初级面试用,一些程序题有答案,例如【程序3】 ...(2)如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数n,重复执行第一步。 (3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。
在计算机编程中,素数检测是一个常见的算法问题。素数是一个只能被1和它...我们只需要测试从2到这个数的平方根之间的所有整数,看这个数是否能被其中任何一个整数整除。 输出:根据测试结果,输出这个数是否是素数。
1.求n个数的最小公倍数。2.水仙花数。3.正整数分解质因数。4.求100-200之间的素数(只能被1和自身整除),并输出。5.非波拉契数列问题。6.sum=a+aa+aaa+aaaa+...7.给一个不多于5位的正整数,求是几位数,并逆序打印...
5.整数a,b的最大公约数是指既能被a整除又能被b整除的最大整数。整数a,b的最小公倍数是指既是a的倍数又是b的倍数的最小整数。编写两个函数,一个函数gcd()的功能是求两个整数的最大公约数,另一个函数mul()的功能是...
JAVA应用程序设计上机报告包含以下几个实验,都是源程序。...A和B,A创建的对象可以计算两个正整数的最大公约数,B创建的对象可以计算两个数的最小公倍数。要求:B类中有一个成员变量是用A类声明;