首页 > 代码库 > 天梯题目解答——1012、1430
天梯题目解答——1012、1430
1012 最大公约数和最小公倍数问题
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,Q是正整数；2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
二个正整数x0,y0
满足条件的所有可能的两个正整数的个数
3 60
4
#include <iostream>using namespace std;#define MAX 10000int LCM(int min, int max, int ev){ int temp; while(min!=0) { temp = min; min = max%min; max = temp; } if(max==ev) return 1; else return 0;}int main(){ int num[MAX]; int x,y; cin >> x >> y; int p[MAX],q[MAX]; int count=0; for(int i=x;i<=y;i+=x) { if(y%i==0){ num[count] = i; cout << num[count] << " "; count++; } } cout << endl; int a,b,k=0; if(y%x==0) { p[0]=x;q[0]=y; cout << x << " " << y << endl; k++; } for(int i=1;i<count;i++) { a = num[i]; for(int j=i+1;j<count;j++) { b = num[j]; if((LCM(a,b,x)) && (a*b/x == y)) { p[k] = a; q[k] = b; k++; cout << a << " " << b << endl; } } } cout << (k<<1); return 0;}
首先对于输入的x,y；找出基 础的num矩阵，num中存储的是[x,y]之间以x为倍数且为y约数的值。
对于num中的值，寻找符合条件的p、q值，可以先判断(x,y)是否满足p、q的要求，只要q为p的倍数即可，比较容易，也可以放在后面一起，只要下面for循环的i从0开始即可。
LCM函数用于判断两个数的最大公约数是否为x，在确定公约数为x的基础上确定是否最小公倍数为y。最大公约数是x、y循环取余，知道最后余数为0，为0时候的分母就是最大公约数，但因为循环判断在交换之后，所以分母已经存到max上了。
最后得出k的个数乘2就是p、q的总个数了。
1430 素数判定
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。
素数在数论中有着很重要的 地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。基于质数定义的基础 之上而建立的问题有很多世界级的难题，如哥德巴赫猜想等。算术基本定理证明每个大于1的正整数都可以写成素数的乘积，并且这种乘积的形式是唯一的。这个定 理的重要一点是，将1排斥在素数集合以外。如果1被认为是素数，那么这些严格的阐述就不得不加上一些限制条件。
概念
只有1和它本身两个约数的自然数，叫质数(Prime Number)。（如：由2÷1=2，2÷2=1，可知2的约数只有1和它本身2这两个约数，所以2就是质数。与之相对立的是合数：“除了1和它本身两个 约数外，还有其它约数的数，叫合数。”如：4÷1=4，4÷2=2，4÷4=1，很显然，4的约数除了1和它本身4这两个约数以外，还有约数2，所以4是 合数。）
100以内的质数有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25个质数。
注：（1）1既不是质数也不是合数。因为它的约数有且只有1这一个约数。
（2）2和3是所有素数中唯一两个连着的数 ．
第一行输入一个正整数n，n<=30000
如果该数是质数，则输出\t
否则输出\n
输入样例1
13
输入样例2
8
样例输出1
\t
样例输出2
\n
#include <iostream>using namespace std;int main(){ int x; cin >> x; if(x==1){ cout << "\\n"; return 0; } else if(x==2 || x==3){ cout << "\\t"; return 0; } int n=2,ev; while(n<x/2) { ev = x%n; if(ev==0){ cout << "\\n"; return 0; } n++; } cout << "\\t"; return 0;}
这题注意下输出就行了。
天梯题目解答——1012、1430