# Can we replace the upper limit condition of the Sieve of Eratosthenes $\sqrt{n}$ with the value $\sqrt{p}$ where $p$ is the last sieved prime $\lt n$?

By chance I stumbled upon the OEIS list A033677 of the smallest divisor of $n$ greater or equal to $\sqrt{n}$. Roughly speaking if we use the classic enhanced sieve of Eratosthenes, $\sqrt{n}$ is the typical upper limit to find a divisor $d \gt 1$ of $n$, so if $n$ is composite then it is expected that $\exists d \in [2,\sqrt{n}]$.

I did the same exercise but instead of $\sqrt{n}$ using as the limit the square root of the last sieved prime, which is indeed the previous closest prime $p$ to $n$ and made the calculation of the smallest divisor of $n$ greater or equal to $\lceil \sqrt{p} \rceil$.

Testing with Python and if I did not make an error, curiously I obtained exactly the same list than A033677 for every $n \in [3,6\cdot 10^6]$ (after that point it gets slower, I will try with PARI\GP later). So I wonder if it is possible to use the above mentioned $\lceil \sqrt{p} \rceil$ upper limit (the ceil of the square root of the last sieved prime) instead of $\sqrt{n}$ to find a divisor of $n$, if any.

This is the (very basic) Python code that compares one by one the elements of the sequence A033677 with the sequence of smallest divisor of $n$ greater or equal to $\sqrt{p}$, please feel free to use it:

from sympy import prevprime, divisors
for n in range (3,10000000):
A0033677_Value=0
for d in divisors(n):
if d>=sqrt(n):
A0033677_Value=d
break

for d in divisors(n):
if d>int(sqrt(prevprime(n))):
if A0033677_Value == d:
print("SUCCESS "+str(n))
else:
print("ERROR " + str(n) + "\t" + str(A0033677_Value)+"\t"+str(prevprime(n))+"\t"+str(d))
return
break


If the observation is true, the property would be something like this:

$\forall n$ (composite)$\ \exists d: d|n\ , d \in [2,\lceil \sqrt{p_1} \rceil], p_1 \in \Bbb P, p_1\lt n,\ \land \not\exists\ p_2: p_1 \lt p_2 \lt n$.

For instance for $n=20,21,22,23$ we would look for a divisor of $n$ in the interval $[2,\lceil \sqrt{19} \rceil]$ because $19$ is the last sieved prime before $n$. As we already sieved $19$ in a former step it is in our list of already available primes and thus we can used (meaning we already know at this point that $19$ is prime). Then applying Eratosthenes as usual it would be detected that $n=20,21,22$ are composite and $n=23$ is the next prime.

UPDATE: as kindly explained by @Slade in the comments, in some cases (e.g when $n$ is a perfect square) having the same divisor $d$ over $\sqrt{n}$ and $\sqrt{p}$ does not imply that we can find a divisor at the interval $[2,\sqrt{p}]$ and it is required to go up to $[2,\lceil \sqrt{p}\rceil]$, meaning that the first divisor is exactly $\lceil \sqrt{p}\rceil$. That is the reason why the ceil function is used to set the upper limit.

If true I am not sure if it might be significant. By Bertrand's postulate, there should be a prime between $[\frac{n}{2},n]$, so in the best of cases, the previous prime would be $p_i=\frac{n}{2}$, so it would imply for that best of cases the use of $\sqrt{\frac{n}{2}}$ as the upper limit for the sieve instead of $\sqrt{n}$.

I would like to ask the following questions:

1. Would it be possible to use $\lceil \sqrt{p} \rceil$ instead of $\sqrt{n}$? Was already in use that approach?

2. Is there a counterexample (probably very big)? If not, what could be the reason behind it? Thank you!

UPDATE: the code below tests the Sieve of Eratosthenes using the modified algorithm as explained above, including the special condition for perfect squares. It seems to work so far up to $10^5$. I will test further.

from gmpy2 import is_prime, is_square
# modified Eratosthenes, upper sieving limit sqrt(p)
lopM= #list of already sieved primes
lp=2 # last prime sieved
for pos in range(3,1000008):
ul=int(sqrt(lp)) #upper limit
if is_square(pos):
ul=ul+1 # correction for perfect squares
# basically: if is a perfect square we would continue for
if ul==1:
ul=2 # exclude 1 of possible divisors
comp=False #composite detected
for j in lopM: # using the list of already known primes
if j in range(2,ul+1): # while j is under the upper limit
if (pos%j)==0:
comp=True
break
else: # we arrived to the upper limit
break
if comp==False:
lopM.append(pos)
lp=pos

for elem in lopM:
if not is_prime(elem): # sanity check
print("ERROR, not prime " + str(elem))
return
print("Primes sieved: " + str(len(lopM)) + " and last prime was " + str(lp))

• Don't you need the Sieve to calculate $p$? In such a case, you can't use $p$ in the Sieve itself. – Crostul Apr 11 '16 at 7:36
• @Crostul I could be wrong but if you are sieving $n$ you already sieved the primes before $n$, so they are available in your list of already sieved primes. – iadvd Apr 11 '16 at 7:39
• @Crostul I have added an example for $n=20,21,22$ using $p=19$. Thank you for the feedback! – iadvd Apr 11 '16 at 7:45
• If I understand correctly, your code is demonstrating that the first divisor $>\sqrt{p}$ is also $\geq \sqrt{n}$. This is a little different from replacing $\sqrt{n}$ by $\sqrt{p}$: for example, if $n=9$, then $p=2$, and we have to search all the way up to $\sqrt{p}+1$ to find a divisor of $n$. – Slade Apr 11 '16 at 8:39
• Right. I was confused by the suggestion of a counter-example. Given $p(\pi(\sqrt{n}))$ if there were a composite of primes g.t. $p$ it would exceed $n.$ So it is just the sieve. – daniel Apr 11 '16 at 15:09

1) As other people stated, imagine $n=q^2$, $q$-prime, then $p_{\pi(q^2)} < q^2 < p_{\pi(q^2)+1}$ which is $\sqrt{p_{\pi(q^2)}} < q < \sqrt{p_{\pi(q^2)+1}}$. Bertrand's postulate is not going to help, because if you stick to any bound $\leq \sqrt{p_{\pi(q^2)}}$, the algorithm will tell you $q^2$ is prime.
2) If $n=q\cdot b$, $q$-prime and $q<b$, then $p_{\pi(n)} < q\cdot b < p_{\pi(n)+1}$. Assuming Oppermann's conjecture is true (some references here), then $q<\sqrt{p_{\pi(n)}}$, otherwise (suppose contrary) if $$\sqrt{p_{\pi(n)}} \leq q \Rightarrow p_{\pi(n)} \leq q^2 < q \cdot (q+1) \leq q\cdot b < p_{\pi(n)+1}$$ and according to that conjecture there will be a prime between $q^2$ and $q \cdot (q+1)$. This contradicts the fact that $p_{\pi(n)+1}$ is the next prime after $p_{\pi(n)}$. So, technically, you can lower the bound in this particular case and assuming Oppermann's conjecture (!)
• great explanation, thank you. I am going to run later a test for 1) because for small integers does not happen as you mention, so I guess this happens for a big counterexample, right? For instance: $101^2=10201$ the previous prime is $10193$ and $\sqrt{10193}=100.9$ as 10201 is a square we jump up to $100+1=101$ as $101$ is in our list of already sieved primes and divides $10201$ then $10201$ is not prime. So this is a counterexample of your explanation at 1)... but I suppose this hold for small integers but not for big integers. I will try to find a counterexample with a Python test. – iadvd Apr 13 '16 at 0:03
• I think that's not a counter example, but rather an example because you are considering $101$ as the lower bound and not any $p$ lower than $p \leq \sqrt{10193}=100.9 < 100+1$ – rtybase Apr 13 '16 at 6:48
• understood, if that is what it means, I agree with the explanation. But that point was added to the question (if I understood correctly the point): in the case of perfect squares the upper bound would be $\lceil \sqrt{p} \rceil$. Indeed the code I added at the end of the question does that. – iadvd Apr 13 '16 at 8:50
• Yep, but I couldn't omit this case, for completeness ;) Also, my previous comment re Andrica's conjecture would suggest $\sqrt{p_{\pi(q^2)}} < q < \sqrt{p_{\pi(q^2)+1}}$ and $\sqrt{p_{\pi(q^2)+1}} - \sqrt{p_{\pi(q^2)}} < 1$ then $\left \lceil \sqrt{p_{\pi(q^2)}} \right \rceil=q$ – rtybase Apr 13 '16 at 9:13