天梯题目解答—

天梯题目解答——1012、1430

1012 最大公约数和最小公倍数问题

题目描述 Description

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件: 1.P,Q是正整数；2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数.

输入描述 Input Description

二个正整数x0,y0

输出描述 Output Description

满足条件的所有可能的两个正整数的个数

样例输入 Sample Input

3 60

样例输出 Sample Output

#include <iostream>
using namespace std;

#define MAX 10000

int 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 素数判定

题目描述 Description

质数又称素数。指在一个大于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是所有素数中唯一两个连着的数．

输入描述 Input Description

第一行输入一个正整数n，n<=30000

输出描述 Output Description

如果该数是质数，则输出

否则输出

样例输入 Sample Input

输入样例1

输入样例2

样例输出 Sample Output

样例输出1

样例输出2

#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;
}

　　这题注意下输出就行了。