題目
最小互質數
我們定義兩個數的互質數當且僅當gcd(a, b) = 1，
現在L手里有n個數，分別為a1，a2，a3 ……an-1，an ，
問，沒有在這n個數中出現過并且與這n個數都互質的最小的數是多少，
LL覺得這個問題太簡單了，于是她把這個問題交給你來解決
輸入
第一行一個數n (1 ≤ n, ai ≤ 10^5)
接下來n行，每行一個數，分別代表a1，a2，a3 ……an-1，an ，
輸出
輸出一行代表答案
樣例輸入
5
1
2
3
4
5
樣例輸出
7
解題思路
這道題如果用暴力破解肯定會TLE，所以我是先用歐拉篩法標記好10^6以內的素數，然后再用sort函式給輸入的資料排好序，從1開始按順序一一往后查找，只要一出現陣列中沒有的數，就判斷是否是質數（利用前面歐拉篩法標記好的的素數陣列），如果是質數，就判斷其是不是陣列中出現過的數的約數，如果不是那么這個數就是答案，如果是，就繼續往后找，
代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;
int prim[N],a[N],i,j,k,n,cnt=0;
bool isp[N]={false};
int main()
{
//歐拉篩法求2~N之間的素數
for(i=2;i<=N;i++){
if(!isp[i]) prim[++cnt]=i;
for(int j=1;j<=cnt;j++){
if(i*prim[j]>N) break;
isp[i*prim[j]]=true;
if(i%prim[j]==0) break;
}
}
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
if(a[1]!=1){
printf("1");//如果陣列中最小的數不是1，則這n個數的最小互質數肯定為1
return 0;
}
for(i=2,k=2;;i++,k++){
bool f=0;
while(a[i+1]!=k+1){//如果a[i+1]!=k+1,則k+1是這個有序陣列沒有出現過的數
if(!isp[k+1]){//判斷是否為素數
if(k+1>a[n]){//如果k+1大于陣列里最大的數，那么它肯定不可能是陣列里任何一個數的約數
printf("%d\n",k+1);
return 0;
}
for(j=i+1;j<=n;j++){//判斷陣列里有沒有數能被k+1整除
if(a[j]%(k+1)==0){
break;
}
}
if(j>n){//陣列內沒有數能被k+1整除，輸出k+1
printf("%d\n",k+1);
return 0;
}
}
k++;//若不符合最小互質數條件，則繼續往后查找
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277141.html
標籤：其他
上一篇：資料結構 堆疊的基礎應用