I am trying to prove the result for a problem which I am unable to do so! The answer is simply $\frac{N}{2}$ when N is even and $\frac{N}{2}+1$ when $N$ is odd. But I do not see why?? Can you give me a formal proof? And a line of thinking for such problems?
The Sieve of Alice, formally defined by the following procedure, which determines the Sieve of Alice up to a given limit $N$.
Create a list of consecutive integers from $N$ to $2$ $\left(N, N-1, N-2,\cdots, 3, 2\right)$. All of those $N-1$ numbers are initially unmarked.
Initially, let $P = N$, and leave this number unmarked.
Mark all the proper divisors of $P$ (i.e. $P$ remains unmarked).
Find the largest unmarked number from $2$ to $P – 1$, and now let $P$ equal this number.
If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.
Unfortunately, Alice has not found an useful application for it's Sieve. But she still wants to know, for a given limit $N$, how many integers will remain unmarked?
$a$ is unmarked if and only if $a>\frac{n}{2}$.
Proof: suppose $a$ has a multiple in interval $[2,n]$. consider the largest multiple of $a$ in the interval $[2,n]$, this number must also be unmarked, but if it is unmarked then $P$ took its value at some point in time, when this happened we marked $a$. On the other hand it is clear the numbers larger than $\frac{n}{2}$ where never marked because $P$ never took the value of a multiple of that number.
Therefore there if $n=2k+1$ the $k+1$ numbers $k+1,k+2\dots 2k+1$ are unmarked and if $n=2k$ the $k$ numbers $k+1,k+2\dots 2k$. So $\lceil \frac{n}{2} \rceil$