c – 同时复杂但运行时间变化很大

以下算法分别具有时间复杂度O(A2.5)和O(Alog(log(A)).仍然对于A(整数)的值大到73939138,第二个算法真的很慢.我试过很多输入,第一个更快.你能解释一下原因吗？

int ul=A/2;
vector <int> answer;
for (int i=1; i<=ul; i++)
{
    if (check(i)==1 && check(A-i)==1 ) //check(i) checks primality of i in O(i^1.5)
   {
       int myint[2] ={ i,A-i };
       answer.assign( myint,myint+2);
       return answer;
   }
}

vector<bool> primes(A+1,truE);
int i,j;
//Sieve of Eratosthenes O(Alog(log(A)))
for(i=2;i*i<A+1;i++)
{
    if(primes[i])
    {
        for(j=2;i*j<A+1;j++)
            primes[i*j]=0;
    }
}
vector<int> arr,answer;
//arr is vector containing all primes from 2 to A; O(A)
for(i=2;i<A+1;i++)
{
    if(primes[i])
        arr.push_BACk(i);
}
i=0;j=arr.size()-1;
//Algorithm to find 2 numbers summing up to a value
while(i<=j)
{
    if(arr[i]+arr[j]>A)
        j--;
    else if(arr[i]+arr[j]<A)
        i++;
    else
    {
        answer.push_BACk(arr[i]);
        answer.push_BACk(arr[j]);
        return answer;
    }
}

编辑：check(n)定义如下：

int check(int n)
{
    int ul=sqrt(n);
    if(n<2)
        return 0;
    for(int i=2; i<=ul; i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;    
}