閱讀434 返回首頁    go 阿裏雲 go 技術社區[雲棲]

龐果網之素因子集合

【題目】

題目詳情

小強最近在學初等數論，老師給他們出了一個課後習題，那就是給你兩個正整數A，B（0<A,B<2^60）,判斷他們的素因子集合是否相同，小強剛接觸數論，想了好一會還是沒能想出來，你能幫助他嗎？

輸入描述：

輸入包含多組測試數據，每組測試數據包含兩個正整數A，B,以文件結束。

輸出描述：

對於每組測試數據如果A和B的素因子集合相同則輸出“YES”，否則輸出“NO”。



答題說明

輸入樣例：

2 8

4 9

10 50

輸出樣例：

YES

NO

YES



【分析】

唯一質因子分解定理：任意一個合數a僅能以一種方式，寫成如下的乘積形式：
a = p1^e1*p2^e2*...*pr^er
    其中pi為素數，p1<p2<...<pr，且ei為正整數。例如數6000=2^4*3*5^3。

【代碼】

/*********************************
*   日期：2014-04-29
*   作者：SJF0115
*   題目: 素因子集合
*   來源：https://hero.csdn.net/Question/Details?ID=506&ExamID=501&from=211
*   結果：AC
*   來源：龐果網
*   總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define N 1000000
long long set[N],set2[N];

//素因子集合
int PrimeSet(long long n,long long *set){
    int num = 0;
    for(long long i = 2;i*i <= n;i++){
        if(n % i == 0){
            set[num++] = i;
            while(n % i ==0){
                n = n / i;
            }
        }//if
    }//for
    if(n > 1){
        set[num++] = n;
    }
    //返回素數集合的個數
    return num;
}

int main(){
    int i;
    long long a,b;
    while(scanf("%lld%lld",&a,&b) != EOF){
        memset(set,0,sizeof(set));
        memset(set2,0,sizeof(set2));
        int num = PrimeSet(a,set);
        int num2 = PrimeSet(b,set2);
        if(num != num2){
            printf("NO\n");
        }
        else{
            for(i = 0;i < num;i++){
                if(set[i] != set2[i]){
                    printf("NO\n");
                    break;
                }
            }//for
            if(i >= num){
                printf("YES\n");
            }//if
        }//if
    }//while
    return 0;
}


最後更新：2017-04-03 12:56:29

  上一篇：go 設計模式六大原則——單一職責原則（SRP）
  下一篇：go JS 回車提交，兼容IE、火狐、Opera、Chrome、Safari……