Difference sets without squares of Integers

Question

I am trying to print numbers occuring in A030193
i.e Let S = set of square numbers;
a(0)=0;
a(n) = smallest m such that m - a(i) is not in S for all i < n.
but I am unable to do it in better than $O(n^2\log{n})$

for (int i = 1 ; i <= n;i++)
{
    for (j = 0  to T.size())
    {
        if (S.find(i-T[j]))
            goto label;
    }   
    T.insert(i);
    label: ;    
}

Here S is Set containing squares and T is set containg numbers of sequence.
Does a better approach exists?

Answer 1

Hint: a sieving method will do it in better than $O(n^2)$. Use a boolean array to represent a subset $A$ of $\{0, \ldots, n\}$. Initially set $A = \{0, \ldots, n\}$. Then for $m$ from $0$ to $n$, if $m \in A$, remove all numbers of the form $m + i^2$, $i > 0$ from $A$. Now the members of $A$ listed in increasing order comprise the $a_i$ with $a_i \le n$.