C - Coprime 2

题意：
给出n个数，在[1,m]范围那找出与这n个数都互质的数。

思路1：

直接暴力，结果不出所料
时间复杂度O（n* m），直接超时
代码：

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a% b);
}
int main()
{
    int i,j;
    int n,m;
    cin>>n>>m;
    int a[100001];
    for(i=0; i<n; i++)="" cin="">>a[i];
    int data[100001];
    long long int o=0;
    long long  int sum;
    o=0;
    for(j=1; j<=m; j++)
    {
        if(gcd(j,a[0])==1)
        {
            data[o]=j;
            o++;
        }
    }
    sum=o;

    for(i=1; i< n ;  i++)
    {
        for(j=0; j < o; j++)
        {
            if( data[j]!=-1)
            {
                if( gcd(data[j],a[i])!=1 )
                {
                    data[j]=-1;
                    sum--;
                }
            }
        }
    }

    cout<< sum << endl;
    for(i=0 ; i< o;  i++)
    {
        if(data[i]!=-1)
            cout<< data[i]<< endl;
    }
    return 0;

}

思路2

做数组data[m]，其中data[j]=0代表数j符合题意，data[j]=1代表不符合题意。
判断a[i]是否为质数，如果是质数则把1~m之间的a[i]的倍数赋值为1；
若不为质数，则把a[i]的质因数，在1~m之间的倍数赋值为1
代码：

**#include <bits/stdc++.h>
using namespace std;


int main()
{
    int i,j;
    int n,m;
    cin>>n>>m;
    int a[100001];
    for(i=0; i<n; i++)   cin>>a[i];
    int data[100001]= {0};
    int sum=m;
    int flag=0;
    int k;
    for(i=0; i<n; i++)
    {
        flag=0;//默认是质数
        if(a[i]==1){flag=1;}
        else
        if(a[i]==2||a[i]==3)
         {
             flag=0;
         }
        else
        {
            for(j=2; j*j<=a[i]; j++)
            {
                if(a[i]%j==0)
                {
                    flag=1;
                     for(k=1;j*k<=m;k++)
                     {
                         if(data[k*j]!=1)
                         {data[k*j]=1;
                         sum--;}
                     }
                    for(k=1;(a[i]/j)*k<=m;k++)
                     {
                         if(data[k*(a[i]/j)]!=1)
                         {data[k*(a[i]/j)]=1;

                         sum--;}
                     }
                }

            }
        }
        if(flag==0)
        {
            for(k=1;a[i]*k<=m;k++)
            {
                if(  data[ a[i]*k ]!=1)
                {data[ a[i]*k ]=1;
                sum--;
                }
            }
        }

    }



    cout<<sum<<endl;
    for(i=1; i<=m; i++)
    {
        if(data[i]==0)
            cout<<i<<endl;
    }
    return 0;

}
**

结果还是超时，但是比暴力快，继续优化。

思路3

思路2超时，应该是因为有公共质因数，重复给data[j]赋值导致，尝试在原函数上修改无果后，开启思路三

可以先把质因数找好标记上 ，然后，那么将不互质的数剔除。

代码：