n^2 ?

我做得也是n^2，但是有人说有更快得方法

我下面的程序应该比n^2更快，但时间复杂度一时算不出来，呵呵。但从测试数据来看，数据量每增加1倍，消耗的时间增加1倍多，因此，时间复杂度应该是接近线性的。
int BinarySearch(int a[], int l, int h, int k)
{
    int        mid;

    while(l <= h)
    {
        mid = (l+h) >> 1;
        if(a[mid] == k)
            return mid;
        else if(a[mid] > k)
            h= mid-1;
        else
            l = mid+1;
    }

    return -1;
}

void sieve(int a[], int n)
{
    int        *b = new int[n];
    int        pos, new_pos;

    memcpy(b, a, sizeof(int)*n);
    for(int i=0; i<n-1; ++i)
    {
        if(a[i] == 0)
            continue;

        pos = i;
        for(int j=a[i]*2; j<=b[n-1]; j+=a[i])
        {
            new_pos = BinarySearch(b, pos+1, n-1, j);
            if(new_pos >= 0)
            {
                a[new_pos] = 0;
                pos = new_pos;
            }
        }
    }
    
    delete []b;
}

nlogn ？

这些数的范围大不大？如果不大，可以用‘筛法’做。

有大数
比如有2 ，6，也有类似于2^200这样的数，数组元素的个数大概是100000

有2^200这样的数，你怎么存放？64位的整数最大才 2^64-1，难道再用数组存放？

是的，我是用java编的，里面可以存2^200的大数

如果有大数，这个方法是不是就不行了啊