首页 > 试题广场 > N-GCD
[编程题]N-GCD
  • 热度指数:3569 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小明很喜欢数对,又很喜欢GCD(最大公约数)。所以他想尽办法创造了一种全新的最大公约数:
给出若干个数对(ai,bi),如果一个最大的质数x可以整除每一个数对中的至少一个数字并且这个数字大于1,那么x就称为这些数对的N-GCD。
现在小明给了你一些数对,希望你可以算出它们的N-GCD。

输入描述:


第一行一个数字n,表示数对的个数。

接下来n行,每行两个数字,用一个空格分隔,表示一个数对。

满足1<=n <=150000,1<=ai,bi<=2 * 10^9。





输出描述:
一个数字,这些数对的N-GCD;若N-GCD不存在,那么输出-1。
示例1

输入

3
2 2
3 6
7 8

输出

2
示例2

输入

2
18 12
3 24

输出

3
先找到输入数字中最小的那个,然后从0到该数字寻找期间出现的素数并记录下来,接着用这些素数一个个去套看能不能除断,如果一对数中两个都不能被该数整除则从素数集中去掉这个数。有可能会出现不止一个公约数的情况, 如:
5
90 108
45 105
75 40
165 175
33 30
其中 5 和 3均为答案,但测试后发现题目想要的是最大的那个故舍去3.
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
bool isPrime(int num) {
	if (num % 6 != 1 && num % 6 != 5) {
		return false;
	}
	for (int i = 6; i <= sqrt(num) + 1; i += 6) {
		if (num % (i - 1) == 0 || num % (i + 1) == 0)
			return false;
		}
	return true;
}
int main() {
	bool isPrime(int num);
	int eNum = 0;
	scanf("%d", &eNum);
	int** data = new int*[eNum];
	long res = -1;
	long min = 0;
	for (int i = 0; i < eNum; i++) {
		data[i] = new int[2];
		scanf("%d %d", &data[i][0], &data[i][1]);
		if (i == 0)
			min = data[i][0];
		min = min < data[i][0] ? min : data[i][0];
		min = min < data[i][1] ? min : data[i][1];
	}
	vector<int> prime = { 2,3 };
	for (int i = 6; i < min; i += 6) {
		if (isPrime(i - 1))
			prime.push_back(i - 1);
		if (isPrime(i + 1))
			prime.push_back(i + 1);
	}
	for (int i = 0; i < eNum; i++) {
		for (int j = 0; j < prime.size(); j++) {
			if (data[i][0] % prime[j] != 0 && data[i][1] % prime[j] != 0)
				prime.erase(prime.begin() + j);
		}
	}
	if (prime.size() == 0)
		cout << -1 << endl;
	else
		cout << prime[prime.size() - 1] << endl;
}


编辑于 2019-09-20 01:14:01 回复(1)
//case通过率90% 的解决思路: 时间复杂度最高是在main()的循环处
//并且 判断是否为质数的复杂度 高于 判断某一质数是否能整数每行中的某个值

// 之前先判断是否为质数,然后判断是否能整除每行当中的某个值,通过率始终为90%
// 改变顺序:先判断是否能整除,然后判断是否为质数,全部通过
# include<iostream>
# include<algorithm>
using namespace std;

bool isZhiShu(long long value){
    for(long long i=2; i<=sqrt(value); i++)
        if(value%i==0)
            return false;
    return true;
}
int main(){
    int n;
    cin>>n;
    long long arr[n][2], limit=2000000001;
    for(int i=0; i<n; i++){
        cin>>arr[i][0]>>arr[i][1];
        limit = min(limit, max(arr[i][0], arr[i][1]));
    }
    int j=0; 
    for(long long i=limit; i>=2; i--){// 从最大值开始依次遍历 
         for(j=0; j<n; j++)
             if(arr[j][0]%i!=0 && arr[j][1]%i!=0)
                 break;
        if(j==n && isZhiShu(i)){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

编辑于 2019-07-31 17:27:38 回复(2)
N-GCD一定不会超过所有数对中的最小数。首先找到这个最小的数,然后从这个数开始自减遍历检验,如果满足N-GCD的条件就退出遍历输出结果。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        ArrayList<int[]> list = new ArrayList(n);
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            String[] temp = br.readLine().trim().split(" ");
            int a = Integer.parseInt(temp[0]), b = Integer.parseInt(temp[1]);
            min = Math.min(min, Math.min(a, b));
            list.add(new int[]{a, b});
        }
        int factor = min;
        while(factor > 1){
            if(!isPrime(factor)) {
                // 因子不是质数直接跳过本次循环
                factor--;
                continue;
            }
            boolean flag = true;
            // 否则检验这个因子是否是N-GCD
            for(int i = 0; i < n; i++){
                if(list.get(i)[0] % factor != 0 && list.get(i)[1] % factor != 0){
                    // 只要有一对数两个数都不能被factor整除,就退出循环
                    flag = false;
                    break;
                }
            }
            if(flag)
                break;
            else
                factor--;
        }
        System.out.println(factor);
    }
    
    private static boolean isPrime(int x){
        for(int i = 2; i < (int)Math.ceil(Math.sqrt(x)); i++){
            if(x % i == 0)
                return false;
        }
        return true;
    }
}


发表于 2021-01-31 10:06:50 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int size=s.nextInt();
        int min=Integer.MAX_VALUE;
        int[] firsts=new int[size];
        int[] seconds=new int[size];
        //读取数组并标记最小数。 可以放入一个数组内。这里为了方便理解用两个数组分开存放
        for(int i=0;i<size;i++){
            int first=s.nextInt();
            int second=s.nextInt();
            firsts[i]=first;
            seconds[i]=second;
            int temp=first>second?second:first;
            if(min>temp){
                min=temp;
            }
        }
        while(min>1){
            //是不是质数
            if(!isPrimeNumber(min)){
                min--;
                continue;
            }
            for(int i=0;i<size;i++){
                if(firsts[i]%min!=0 && seconds[i]%min!=0){
                   min--;
                    break;
                }
                //全数对扫描完成复核条件,直接输出
                if(i==size-1){
                    System.out.println(min);
                    return;
                }
            }
        }
        System.out.println(-1);
    }
    
    public static boolean isPrimeNumber(int num){
        for(int i=2;i<num;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }
    
}

发表于 2020-07-26 18:43:57 回复(0)
/*您的代码已保存 运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出 
case通过率为70.00%*/
import java.util.*; public class Main{     public static void main(String[] org){         Scanner scan = new Scanner(System.in);         int n = scan.nextInt();         scan.nextLine();         int[] s = new int[n*2];         int[] s1 = new int[2*n];         for(int i=0;i<2*n;i++){             s[i] = scan.nextInt();         }         s1 = s.clone();         int x=-1;         for(int i=2;i<=getMin(s1);i++){          int h=0;             if(isZhiShu(i)){              for(int j=0;j<n*2;j++){                   if(isZhengChu(s[j],s[j+1],i)){                     h++;                     if(h==n){                         if(x<i){                            x=i;                         }                     }                   }                     j++;                  }             }                      }         System.out.println(x);     }     public static int getMin(int[] s1){         Arrays.sort(s1);         return s1[0];     }     public static boolean isZhiShu(int x){         for(int i=2;i<x;i++){             if((x%i)==0){                 return false;             }         }         return true;     }     public static boolean isZhengChu(int a,int b,int x){         if((a%x)==0||(b%x)==0){             return true;         }else             return false;     } }



编辑于 2020-07-21 13:39:43 回复(0)
/*对任意一组分解质因数(这里选和最小的),遍历所有组,不满足条件(整除任意组的至少一个数)的删除
最后看剩下的有无,没有-1.有输出最大的*/
#include <bits/stdc++.h>
#define LL long long 
using namespace std;
const int AX = 2e5 + 666 ; 
struct Node{
    LL x ;
    LL y ;
    bool operator < ( const Node &a )const{
        return ( x + y ) < ( a.x + a.y ) ; 
    }
}a[AX];
set<LL>s ;

void get_PrimeFac( LL x ){
    for( LL i = 2 ; i * i <= x ; i++ ){
        if( x % i == 0 ){
            s.insert(i) ; 
            while( x % i == 0 ){
                x /= i ;
            }
        }
    }
    if( x > 1 ) s.insert(x) ; 
}

int main(){
    int n ;
    scanf("%d",&n) ;
    LL x , y ; 
    for( int i = 0 ; i < n ; i++ ){
        scanf("%lld%lld",&a[i].x,&a[i].y) ; 
    }
    sort( a , a + n ) ; 
    get_PrimeFac(a[0].x);
    get_PrimeFac(a[0].y);
    set<LL>::iterator it , tmp ;
    
    if( s.size() ){
        for( int i = 1 ; i < n ; i++ ){
            it = s.begin() ; //放错位置找了半天- -。
            while( it != s.end() ){
                if( ( a[i].x % (*it) ) && ( a[i].y % (*it) ) ){
                    tmp = it ;
                    it++ ; 
                    s.erase(tmp) ;
                }else it++ ; 
            } 
        }   
    }
    if( !s.size() ){
        cout << -1 << endl;
    }else{
        it = s.end() ; it--;
        cout << *it << endl;
    }
    return 0 ; 
}

发表于 2020-02-11 15:28:19 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool P(int n){
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0)
            return false;
    return true;
}

int main(){
    int n;
    cin>>n;
    int a[n],b[n],m=INT_MAX;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        m = min(m, a[i]);
        m = min(m, b[i]);
    }
    while(m>1){
        if(((m&1)==0 && m!=2) || (!P(m))){
            m--;
            continue;
        }
        bool flag = true;
        for(int i=0;i<n;i++){
            if(!((a[i]%m==0) || (b[i]%m==0))){
                flag = false;
                break;
            }
        }
        if(flag)
            break;
        else
            m--;
    }
    cout<<((m==1)?-1:m)<<endl;
    
    return 0;
}

发表于 2019-09-06 01:19:15 回复(0)
case通过率90%,思路是选取第一对整数,在第一对整数中按从大到小的顺序选择出可能的结果
(pair[0][0]%i==0 || pair[0][1]%i==0) && isPrime(i)
添加到一个队列当中,然后再遍历pair,
如果当前数字满足,continue;
否则选择队列的下一个数字
import java.io.*;
import java.util.ArrayList;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[][] pair=new int[n][2];
        for(int i=0;i<n;i++){
            String[] line=br.readLine().split(" ");
            pair[i][0]=Integer.parseInt(line[0]);
            pair[i][1]=Integer.parseInt(line[1]);
        }
        ArrayList<Integer> GCD=new ArrayList<>();
        for(int i=Math.max(pair[0][0],pair[0][1]);i>1;i--){
            if((pair[0][0]%i==0 || pair[0][1]%i==0) && isPrime(i)){
                GCD.add(i);
            }
        }
        int index=0;
        int len=GCD.size();
        for(int i=1;i<n;i++){
            if(pair[i][0]%GCD.get(index)==0 || pair[i][1]%GCD.get(index)==0){
                continue;
            }
            while(index<len && pair[i][0]%GCD.get(index)!=0 && pair[i][1]%GCD.get(index)!=0){
                index++;
            }
            if(index==n){
                System.out.println(-1);
                return;
            }
        }
        System.out.println(GCD.get(index));
    }
    public static boolean isPrime(int num){
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }
}


发表于 2019-08-30 19:45:21 回复(0)
思路:从所有数对里取最小值。从这个最小值一直遍历到2。找到最大的那个质数,满足能整除的条件。
质数的判断:1.大于2的偶数不可以是质数。所以最小值是大于2的偶数直接减一。
                      2.质数判断的开始条件是3,结束条件是sqrt(X),而不是x-1。同样步长也是2,因为奇数不可能被偶数整除。
                      3.类似1,当一个奇数不满足条件后,要减2判断下一个奇数。
n = int(input().strip())
nums = []
min_num = float("inf")
for _ in range(n):
    num_group = list(map(int, input().strip().split(" ")))
    min_num = min(min_num, min(num_group))
    nums.append(num_group)
 
 
def is_ok(div):
    for num2 in nums:
        if num2[0] % div != 0 and num2[1] % div != 0:
            return False
    return True
 
 
tmp = min_num
if tmp > 2 and tmp % 2 == 0:  # 如果最小值是大于2的偶数,减一
    tmp -= 1
 
status = 0
while not status and tmp > 1: # 不是质数,或者不能满足数对整除,则一直往下减。
    status = 1
    i = int(pow(tmp, 0.5))+1 # 结束条件,没有奇数可以被大于它的平方根的数整除,所以往后不需要在检查。
    for j in range(3, i, 2):  # 步长依旧是二,奇数tmp不可以被偶数i整除。
        if (tmp % j) == 0:
            status = 0
            break
    if status:
        if is_ok(tmp):
            break
        else:
            status = 0
    tmp -= 2  # 每次减2,还是因为偶数不是质数
 
if status:
    print(tmp)
else:
    print(-1)


发表于 2019-08-28 14:34:04 回复(2)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
bool isP(int n){
    for (int j=2;j<=n/2;++j){
        if (n%j==0) return 0;
    }
    return 1;
}
vector<int> get(int a,int b){
    vector<int> ysy;
    //ysy.push_back(2);
    for (int j=2;j<=max(a,b);++j){
        if ((a%j==0 || b%j==0 )&& isP(j)) ysy.push_back(j);
    }
    return ysy;
}
int n,a,b;
int main(){
    scanf("%d",&n);
    int dp[n][2];
    vector<int> ans;
    long mymin=2000000001;
    for (int i=0;i<n;++i){
        scanf("%d %d",&dp[i][0],&dp[i][1]);
        if (mymin>max(dp[i][0],dp[i][1])){
            a=dp[i][0];
            b=dp[i][1];
            mymin=max(dp[i][0],dp[i][1]);
        }
    }
    ans=get(a,b);
    int i=0;
    for (;i<n;++i){
        if (ans.size()==0) break;
        a=dp[i][0];
        b=dp[i][1];
        vector<int> tmp;
        vector<int>::iterator iter;
        for (iter=ans.begin();iter!=ans.end();iter++){
            if (a%*iter==0 or b%*iter==0) tmp.push_back(*iter);
        }
        ans=tmp;
    }
    if (i==n) cout<<ans.back()<<endl;
    else cout<<-1<<endl;
}


发表于 2019-05-06 18:03:35 回复(0)
import sys
n = int(input())
pairs = []
for line in sys.stdin:
    pairs.append(list(map(int, list(line.split()))))
    
def isprime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True
def cal(n):
    res = []
    for i in range(2, n + 1):
        if n%i == 0 and isprime(i):
            res.append(i)
    return res

def solution(l):
    res = -1
    for n in l:
        for a, b in pairs:
            if not (a%n == 0&nbs***bsp;b%n == 0):
                break
        else:
            return n
    return -1

a, b = min(pairs, key=lambda x:max(x))
l = cal(a) + cal(b)
l.sort(reverse=True)
print(solution(l))

发表于 2020-08-05 22:44:28 回复(0)
1
16 34
这种素数不超过16的方法对吗
发表于 2020-07-31 18:00:22 回复(0)
###素数表的可以通过
###DP未通过,40%case,显示语法错误和越界,有大佬能帮忙解答一下吗


def fig(num):
    if num==2:
        return True
    length = max(int(pow(num,0.5))+1,3)
    for i in range(2,length):
        if num%i==0:
            return False
    return True  
def dp(dui):
    def find_yue(dui,yue):
        if yue==[]:
            return -1
        if dui==[]:
            return yue
        new_yue = []
        for i in yue:
            if dui[0][0]%i==0 or dui[0][1]%i==0:
                new_yue.append(i)
        dui.remove(dui[0])
        return find_yue(dui,new_yue)


    yue = [i+1 for i in range(1,max(dui[0]))]
    out = find_yue(dui,yue)
    if out==-1:
        print(-1)
    else:
        lth = len(out)
        for i in range(lth):
            if fig(out[lth-i-1]):
                print(out[lth-i-1])
                break
def prtable(dui,mi):
    tab = []
    for i in range(2,mi+1):
        if fig(i):
            tab.append(i)
    for i in range(len(dui)):
        for j in tab:
            if dui[i][0]%j and dui[i][1]%j:
                tab.remove(j)
    if tab==[]:
        print(-1)
    else:
        print(tab[-1])
                
    return 0
if __name__=='__main__':
    n = int(input())
    dui = []
    mi=2*10e9
    for i in range(n):
        _dui = list(map(lambda x:int(x),input().split(' ')))
        mi = min(mi,min(_dui))
        dui.append(_dui)
    
    #dp(dui)
    prtable(dui,mi)

发表于 2020-07-30 16:58:41 回复(0)

分析

在读取数字的时候顺便计算下最小值min,之后找出[2,min]之间的素数,并从大到小遍历,判断该数能否整除除nums数组中每一个数对中的任意一个值。

from math import sqrt

def is_prime(a):
    for i in range(2,int(sqrt(a)+1)):
        if a%i==0:
            return False
    return True

N = int(input())
nums = []
min_val = 1e9
for i in range(N):
    val1,val2 = list(map(int,input().split()))
    min_val = min(min_val,val1,val2)
    nums.append([val1,val2])

primes = []
res = 1e9
for i in range(min_val,1,-1):
    if is_prime(i):
        primes.append(i)

for val in primes:
    satisfied = True
    for i in range(N):
        if nums[i][0]%val!=0 and nums[i][1]%val!=0:
            satisfied = False
            break
    if satisfied:
        res = val
        break

print(res) if res!=1e9 else print(-1)
发表于 2020-07-15 18:11:14 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool isPrime(long long n)              // 判断n是不是质数
{
    for(int i=2;i<=sqrt(n);i++)        //注意从2开始  终止条件是根号
        if(n%i==0)
            return false;
    return true;
}
int main()
{
    long long n,res=-1;
    cin>>n;
    vector<vector<long long>>num;
    vector<long long> temp(2);
    long long minNum=LONG_LONG_MAX;
    
    for(int i=0;i<n;i++)
    {
        cin>>temp[0];
        cin>>temp[1];
        minNum=min(minNum,min(temp[0],temp[1]));  //找到数对中的最小值 
        num.push_back(temp);
    }
    
    for(long long j=minNum+1;j>=2;j--)      //从最小值开始从后往前
    {
        bool breakLoop=false;
        for(auto vec:num)
        {
            if(vec[0]%j!=0&&vec[1]%j!=0)    //如果都不能整除则跳出
            {
                breakLoop=true;
                break;
            }
        }
        if(breakLoop) continue;  
            if(isPrime(j))                  //是质数,找到答案
            {
                res=j;
                break;
            }
    }
    cout<<res<<endl;
}

发表于 2020-06-30 19:55:36 回复(0)
我服了,这也能交动态规划??这题目分类有问题把
发表于 2020-06-27 19:58:09 回复(0)
思路不是很难,但minValue的设置不熟悉,搞了很久才发现是最小值的初值给的有问题,坑

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int findGCD(int n) {

	int ans = -1;
	vector<vector<int>> nums(n, vector<int>());
	int minValue = 2000000001;
    //cout << n << endl;
	for (int i = 0; i < n; i++) {
		int v1 = 0; 
        int v2 = 0;
		cin >> v1 >> v2;
        //cout << v1 << " " << v2 << endl;
		nums[i].push_back(v1);
		nums[i].push_back(v2);
        //cout << minValue << endl;
		minValue = min(minValue, max(v1, v2));
        //cout << minValue << "  " << i << endl;
	}

	//获取可能的非质数公约数
	int numsGcds = minValue;   //不能进行开方,因为数字本身可能为质数
	vector<int> gcds(numsGcds+1, 1);
	gcds[0] = 0;
	gcds[1] = 0;
    //cout << numsGcds << "ji " << endl;
	for (int i = 2; i <= numsGcds; i++) {
		if (gcds[i]) {
			gcds[i] = i;
			for (int j = i + i; j <= numsGcds; ) {
				gcds[j] = 0;
				j = j + i;
			}
		}
	}

	for (int i = 0; i < gcds.size(); i++) {
		if (gcds[i]) {
			int tempAns = gcds[i];
            //cout << tempAns << endl;
			bool ok = true;
			for (int j = 0; j < nums.size(); j++) {
                
				if (nums[j][0] % tempAns == 0 || nums[j][1] % tempAns == 0) {
					continue;
				}
				else {
					ok = false;
					break;
				}
			}

			if (ok) {
				ans = max(ans, tempAns);
                //cout << ans << endl;
			}
		}
	}

	return ans;
}

int main() {

	int n;
	cin >> n;
	int ans = findGCD(n);
	cout << ans << endl;
	//system("Pause");
	return 0;
}

发表于 2020-06-15 12:10:24 回复(0)
#include<bits/stdc++.h>
using namespace std;
vector<int>v;
void func(vector<int>& v){
    int n = v.size()-1;
    for(int i=1;i<=n;++i){
        if(i&1) v[i]=1;
        else v[i] = 0;
    }
    for(int i=3;i<=n;++i)
    {
        if(v[i]){
            for(int j=i+i;j<=n;j+=i)
                v[j]=0;
        }
    }
}
int main(){
    int n;
    cin>>n;
    vector<int>A(n);
    vector<int>B(n);
    // m的可取值范围从每组的最大值的集合中的最小值递减到2
    int m = INT_MAX;
    for(int i=0;i<n;++i){
        cin>>A[i]>>B[i];
        m = min(m,max(A[i],B[i]));
    }
    //素数筛法 确定2~m的素数
    v.resize(m+1);
    func(v);
    v[2]=1;
    while(m>1){
        if(!v[m])
           {
               if(m&1) m-=2;
               else m-=1;
               continue;
           }
        int i;
        for(i=0;i<n;++i){
            if(!(A[i]%m==0||B[i]%m==0))
            {
                break;
            }

        }
        if(i!=n) m--;
        else break;
    }
           cout<<(m==1?-1:m)<<endl;
    return 0;
}
发表于 2020-06-06 11:10:43 回复(0)
高赞回复的Java实现,思路确实比较非常容易理解
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * @Author: coderjjp
 * @Date: 2020-05-09 13:48
 * @Description: 数对的N-GCD
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int eNum = Integer.valueOf(br.readLine());
        int data[][] = new int[eNum][2];
        long min = 0;
        String linex[];
        for (int i = 0; i < eNum; i++) {
            linex = br.readLine().split(" ");
            data[i][0] = Integer.valueOf(linex[0]);
            data[i][1] = Integer.valueOf(linex[1]);
            if (i == 0)
                min = data[i][0];
            min = Math.min(min, data[i][0]);
            min = Math.min(min, data[i][0]);
        }
        ArrayList<Integer> prime = new ArrayList<>();
        for (int i = 2; i <= min; i++)
            if (isPrime(i))
                prime.add(i);
        for (int i = 0; i < eNum; i++)
            for (int j = 0; j < prime.size(); j++)
                if (data[i][0] % prime.get(j) != 0 && data[i][1] % prime.get(j) != 0)
                    prime.remove(j);
        if (prime.size() == 0)
            System.out.println(-1);
        else
            System.out.println(prime.get(prime.size() - 1));
    }

    private static boolean isPrime(int a) {
        for(int i = 2; i <= Math.sqrt(a); i++)
            if (a % i == 0)
                return false;
        return true;
    }
}

发表于 2020-05-09 16:27:36 回复(0)
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();//数对的个数
        int[][] pair = new int[n][2];//数对
        int upLimit = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            pair[i][0] = a;
            pair[i][1] = b;
            int tempMax = Math.max(a, b);
            upLimit = Math.min(upLimit, tempMax);
        }
        boolean flag = true;
        boolean found = false;
        for (int i = upLimit; i >= 2; i--) {
            if (isPrime(i)) {
                for (int j = 0; j < n; j++) {
                    int a = pair[j][0];
                    int b = pair[j][1];
                    if (a % i != 0 && b % i != 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    System.out.println(i);
                    found = true;
                    break;
                }
                flag = true;
            }
        }
        if(!found){
            System.out.println(-1);
        }
    }

    private static boolean isPrime(int num) {
        if (num > 2 && (num & 1) == 0) {
            return false;
        } else if (num == 2) {
            return true;
        }
        for (int i = 3; i <= Math.floor(Math.sqrt(num)); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

发表于 2020-04-05 04:30:43 回复(0)