Yes, but only after we have stated what is considered memory used by an algorithm or program.
For this particular problem, I would like to use one of the simplest choices. The memory used by the program is the extra or temporary space used excluding the input and output. Furthermore, each variable (that does not share its storage with others) uses a unit of space. One might argue the output should count towards memory usage. My point is to let us choose a usage model so that we can concentrate on the most relevant and interesting part, although in another situation, how to reduce the memory used by the output might be the more significant part.
Here is the snippet that use 3 units of memory, where I remove the call to sqrt(i)
. Each of $n$, $i$, $j$ uses 1 unit of memory. I comment out the output code to make it clear that its memory usage is not considered.
int n = N; // N should be given elsewhere
for (int i=2; i<n; i++)
for (int j=2;; j++)
{
if ( j*j > i) {
// cout << i << " ";
} else if (i % j == 0)
break;
}
But wait, how can we check j*j > i
? Even if we assume the computing machine can compute j*j
magically without using extra memory, it still needs to store the result of j*j
so as to compare with i
. So it is only reasonable that we add 1 or more unit of memory usage here. Then how about i % j
? We would like add 1 or more unit of memory usage here.
If we dig deeper, we will ask whether those 2
and 0
in the program count towards memory or not. We may have to ask during the program execution, doesn't it need to use some space to remember where it is executing and how to jump around? If those memory are needed, can we reuse them during different execution time?
The more we study this way, the more uncertain the answer becomes. This is, in fact, the truth. It is almost impossible to get an accurate usage of memory theoretically unless we have an accurate model of storage and computation specified down to the bit. When we do have that accurate model, an accurate analysis to the bit may become so tedious and distracting we might lose the big picture.
The way out to get a healthy picture is the big $O$ or $\Theta$ notation. We will simply say that this program use $O(1)$ or $\Theta(1)$ memory. That is, for a reasonable model of storage and computation, there is a constant $C$, for any give $N$, the program will use less than $C$ units of memory. In practice, we usually mean a small or reasonable $C$.
By the way, the program in the question misses primes 2 and 3.
sqrt(n)
can be eliminated. $\endgroup$