\(\gcd(a,b) \neq 1\) means \(a\) and \(b\) have a common divisor.
Therefore, the following solution is valid, just as the Eratosthenes’ sieve:

• Add \(S\) to every integers from \(1\) through \(M\), inclusive.
• For \(i\) from \(1\) to \(N\), inclusive, repeat the following:
  • Factorize \(A_i\) into primes. Let \(P\) be the set of its prime factors.
  • For every prime factor \(k\) in \(P\), remove all multiples of \(k\) from \(S\).
  • Note that the computational complexity can be improved by avoiding the operation above for the same prime more than once. (Without this, you will get TLE (Time Limit Exceeded))
• The integers remaining in \(S\) after all the operations is the solution.

The complexity depends on implementation. By doing the prime factorizations in a total of \(O(\sqrt{\max A})\) time, the solution of at worst \(O(N \sqrt{\max A})\) is accomplished.

Sample Code (C++)

#include<bits/stdc++.h>
#define SIZE 100005

using namespace std;

vector<int> pfact(int x){
  vector<int> res;
  for(int i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res.push_back(i);
    }
  }
  if(x!=1){res.push_back(x);}
  return res;
}

int main(){
  int n,m;
  cin >> n >> m;
  vector<bool> fl(SIZE,true);
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    vector<int> v=pfact(a);
    for(auto &nx : v){
      if(fl[nx]){
        for(int j=nx;j<SIZE;j+=nx){fl[j]=false;}
      }
    }
  }
  vector<int> res;
  for(int i=1;i<=m;i++){
    if(fl[i]){res.push_back(i);}
  }
  cout << res.size() << '\n';
  for(auto &nx : res){cout << nx << '\n';}
  return 0;
}