[Question]
  [
[Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes?wprov=sfla1) is a method for finding prime numbers:  
take the sequence of all positive integer numbers starting from 2 then for each remaining number drop all its multiples.
```
2 3 x 5 x 7 x 9 x 11 x 13 x 15 x 17 x ...
2 3 _ 5 _ 7 _ x _ 11 _ 13 _  x _ 17 x ...
```
**Task**
Given a number \$n \ge 2\$, find the minimum amount of numbers you have to drop before you can determine whether *n* is a prime number or not using the Sieve of Eratosthenes.
For example if you want to check if \$15\$ is prime you start dropping multiples of \$2\$:  
`2 3 x 5 x 7 x 9 x 11 x 13 x 15 ..`  
then \$3\$:  
`2 3 _ 5 _ 7 _ x _ 11 _ 13 _ X ..`
Here we are! 15 was dropped so it's not prime.  
We dropped 8 numbers.
Note that we don't need to check more numbers.  
That is, you don't have to find how many *not-primes* are there.
Note also that if the number you are testing is prime then you have to try all numbers up to it( without considering optimizations) , and you have to drop all not primes actually in that case.
**Test cases**
Terms for *n* from 2 to 100
```
0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 8, 7, 9, 8, 10, 9, 12, 10, 13, 11, 15, 12, 16, 13, 18, 14, 19, 15, 20, 16, 23, 17, 24, 18, 24, 19, 27, 20, 28, 21, 28, 22, 31, 23, 33, 24, 32, 25, 36, 26, 37, 27, 36, 28, 41, 29, 42, 30, 40, 31, 45, 32, 47, 33, 44, 34, 50, 35, 51, 36, 48, 37, 55, 38, 56, 39, 52, 40, 59, 41, 59, 42, 56, 43, 64, 44, 66, 45, 60, 46, 67, 47, 71, 48, 64, 49
```
**Rules**
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), the aim is to have the shortest code(in bytes) possible within the respect of golfing rules.
This is also [sequence](/questions/tagged/sequence "show questions tagged 'sequence'") so as usual you can output:
* *n-th* term.
* First *n* terms.
* The infinite sequence.
Where *n* refers to the actual number you have to check so the sequence starts at \$n = 2\$.
You can include 0 and 1, however those are considered undefined behaviour so the result doesn't matter.
[Sandbox](https://codegolf.meta.stackexchange.com/a/24646/84844)
  
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~40 68 ...~~ 60 bytes
```
->n,*w{4.step(n,2){|x|w[-1]==n||w|=[*x.step(n,x/2)]};w.size}
```
[Try it online!](https://tio.run/##KypNqvyfZvtf1y5PR6u82kSvuCS1QCNPx0izuqaipjxa1zDW1javpqa8xjZaqwImW6FvpBlba12uV5xZlVr7v0BBw0hPz9DAQFMvN7FAQy1N8z8A "Ruby – Try It Online")
Reverse sieve: start with an empty set, add all multiples of numbers in the range (2..n) unless n is in the set. The result is the size of the final set.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 19 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
ÅP©÷L€¦®*˜ÙIpigëIk>
```
Outputs the \$n^{th}\$ term.
[Try it online](https://tio.run/##ASkA1v9vc2FiaWX//8OFUMKpw7dM4oKswqbCrirLnMOZSXBpZ8OrSWs@//8xNQ) or [verify the first 23 test cases](https://tio.run/##AT0Awv9vc2FiaWX/MjVMwqZ2eT8iIOKGkiAiP3nDkFX/w4VQwqnDt0zigqzCpsKuKsucw5lYcGlnw6tYaz7/fSz/) or [see this for a step-by-step outout](https://tio.run/##VZCxSsRAEIb7e4ohpdwVKWxO9BBBCCiIaCUWm8skGW6zu5fdRG0FH0KwFkSx1D5X@ha@SNxk9lDbne@b/9/RVqSEfR8lyjRuDtF0v/tYTKJDKcHUVKGFFKW@AV0DrhshwWlwJVmgrbB5OOte2EqUwwLrWUYtZeg5ZAzSO0CxLEHnw6PFsHvUP9m9qIWyua4rJkn5IAFX8bS9Bkl2jDph9Bwr3fJ6iSIjVUAMea1ZHcDv@7fumeHTRjoyMhTwRchZjh/A7n2HsWMpnEPFS0Pc1xPPLhWtG8oHdWz8yM9HJS5XQPmff/q7iN/liQlnyb3pZ3Mw2oBQGZjGlqG/Ktz2LmPw3oQCDkr7vALdOItnqbCY@aAMb7dCSP1fm4rNa7I6WPR9vPsD).
**Explanation:**
```
ÅP        # Get all prime numbers up to and including the (implicit) input
  ©       # Store this in variable `®` (without popping)
   ÷      # Integer-divide the (implicit) input by each of these primes
    L     # Transform each value into a [1,v] ranged list
     €¦   # Remove the leading 1 from each to make the range [2,v]
       ®* # Multiply each list by its prime from variable `®`
          # (we now have a list of lists of prime-multiples up to the input)
˜         # Flatten this list of lists
 Ù        # Uniquify it
  Ipi     # If the input itself is a prime:
     g    #  Pop the list and push its length
    ë     # Else:
     Ik>  #  Push the input's 1-based index instead
          # (after which the result is output implicitly)
```
[Answer]
# [Python 3](https://docs.python.org/3/), 99 bytes
Pretty straightforward implementation of the sieve which stops updating values as soon as `n` has been marked as composite.
```
def f(n):
 r=[0]*-~n
 for p in range(2,n):r[p*p::p]=[v>=r[p]|r[n]for v in r[p*p::p]]
 return sum(r)
```
[Try it online!](https://tio.run/##TcxBCgIxDIXh/Zwiy2ZQqLor1IuELARb7cJMiJ2BAfHqtSMILh/v49e13ic5tXZNGbITDANYJM/j/i0D5MlAoQjYRW7JHXcdGOmoIShHWs6xL34ZCW90@dLfzz2V6mwCz/nhDJtakeoou4KbLv9hOHiPjO0D "Python 3 – Try It Online")
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 53 bytes
```
.+
$*,
$.`$*
^..
+1`(?=.*1$)(,(1+),.*?,)\2+\b
$1#
#
```
[Try it online!](https://tio.run/##K0otycxL/K@nzaWidWgbF5eKXgKXkWMCl6qGewJEVAcsqKLFFaenx8WlbZigYW@rp2Wooqmho2Goramjp2WvoxljpB2TxKViqMyl/P@/oSkA "Retina 0.8.2 – Try It Online") Link is to test suite that outputs all the values from `2` to `n`. Explanation:
```
.+
$*,
$.`$*
^..
```
List all the values from `2` to `n` in unary with leading commas.
```
1`(?=.*1$)(,(1+),.*?,)\2+\b
$1#
```
Unless `n` has been replaced with a `#`, replace the smallest composite number divisible by the smallest possible prime with a `#`.
```
+`
```
Repeat until either `n` or all the composite numbers have been replaced with a `#`.
```
#
```
Output the number of integers that were replaced with a `#`.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 13 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ḊÆfḢ$ÞẒÐḟ⁸0¦i
```
A monadic Link that accepts an integer, `n`, and yields an integer.
**[Try it online!](https://tio.run/##AScA2P9qZWxsef//4biKw4Zm4biiJMOe4bqSw5DhuJ/igbgwwqZp////MTU "Jelly – Try It Online")**
### How?
```
ḊÆfḢ$ÞẒÐḟ⁸0¦i - Link: n
Ḋ             - dequeue n -> [2,3,4,...,n]
     Þ        - sort by:
    $         -   last two links as a monad:
 Æf           -     prime decomposition e.g. 63 -> [3,3,7]
   Ḣ          -     head -> minimum prime factor    ^
       Ðḟ     - filter discard those for which:
      Ẓ       -   is prime?
           ¦  - sparse application...
          0   - ...to indices: zero (rightmost)
         ⁸    - ...apply: chain's left argument, n
                ...(this makes the rightmost entry, if there is one, become n)
            i - first 1-indexed index of n (zero if n is not found)
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 94 bytes
```
c;j;i;*s;f(n){s=calloc(n,4);for(c=j=i=1;++i<n&j!=n;)for(s[j=i]=1;j<n;j+=i)c+=!s[j]++;c-=j!=n;}
```
[Try it online!](https://tio.run/##VZJhb5swEIa/91e4kTpBIBo2NhQ53pdpv6LhA3JMB0udCiI1WpS/Pnbnc9M2Ooh5773nMD67ebZ2Wawe9aDXs@4Tn15mY7vD4WgTn8tU98cpsWY0g@E6y4at/zbeG69T1Ocn0FtIjFuvx8wMqc3MPahtlmm7McF5XQZ/Yi/d4JOUXe4Y/FBw51dnT27/1DLDLkXOIHgIEaLMmQyhQlQhHnNW56wJC16EFRe05FDAEaCiVkUNrYDhDeVEQTmBOYAJSR4RPaImj0CNx398H041ZUneEl8TeCWy4Cprqg3PUCPRDzyJtcCTBTGkolpZE0siC7eJedwrJ4Z8JKZCP6wV9gCeEsRSDfVQsQfmJfAqScyqol4V9savV1PPmhM7@JqrDgdij34@Mfu7m9Zwd/aPm@hcVrvzL7E7Nz/hUqucfX4uV7EaRoEleKaD37szlBU6LrdsHv66Y5@8n3b6PQrrm6IZjBW60wCjCXmfEg80QmVM6C@pDlI4r19VB@pttEJl@2F4ncDSJ6uHPdv8YHB/mHceduVz1uW3jXfGuPYTtp@cS@YoXO@uyz/bH7rnedm8/Qc "C (gcc) – Try It Online")
Inputs an integer \$n\ge 2\$.  
Returns the \$n^{\text{th}}\$ term.
[Answer]
# [Python](https://www.python.org), 95 bytes
```
f=lambda n:(g:=lambda x:(g([i for i in x if i%min(x)])if n in x else n-len(x))-1)(range(2,n+1))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY349NscxJzk1ISFfKsNNKtYJwKIEcjOlMhLb9IIVMhM0-hQiEzTSFTNTczT6NCM1YTyMmDCKfmFKcq5OnmpIIkNHUNNTWKEvPSUzWMdPK0DTU1odYoFxRl5pVoRKdpZGrCzYQpVDA0MACaCVEKcxkA)
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), ~~38~~ 34 bytes
-4 bytes by adapting @Kevin Cruijssen's [05AB1E answer](https://codegolf.stackexchange.com/a/245976/98547)
```
{(#r)^(0,r:?,/(x<)_'n*/:n:2+!x)?x}
```
[Try it online!](https://ngn.codeberg.page/k/#eJwtkd1unDAQhe/9FFO1UnZbCP4Z2xgq5SV6FyUN2kJYJYtboC2rKH32ztjIA7ZnzvnGhqF5O3ycj48HWczNXVEdtq/H7zfT56qZGv3lw3a8296FmBsJEhQNTcMA0rA0HI0aPAR6K0mT0jwrA4rENm1d2lIdQQVOaslJTUkPGrmkU0l7LmnaqvSmRoplxrDAUGcLhowOjGcxr2tA0gRAEktAyRa0LEbPRiQjHZXydFzFFqzZbklTgyVUAKvZaAOjbEJRHg04ZLtzDHQEp8t6xnrFEK4GIdbm7dP99d/cDACwtU/xpT08Dd35td3aazsfH97FenNPXzKEdn4QohLjuv5cmqo6xR/9c3wdbpe1O73022nspuf+9hQv1a/f/bKe47RUGm3wWI3xb3nppmu5nPs/fRmHsp+7NS7r2E/9Uo7ndRHiWz9fFhjiDBMMc7zQn1oj/Q4phCyAQqXQKUwBmMKmcCnqAnwBIS2UTCul81KRQTHA7jm351hKGBVyTctc01wjmMas0btG+6zRnFP7zOdR2WNM1ho+JvEMs+gxPnvTnjzIeuIhe4mHMjPQZi/6zEJm8TW5zndVmYF1ZlrW09pyD+JZnVk25B5278F1JJ7DzHQu93Lcm7+ezz29yuykC+I/kA6z1Q==)
Outputs the *n-th* term (referred to within the code as `x`).
* `(...)?x` find the 0-based index of `x` in the list generated by `(...)` (returning `0N`, the integer null, if `x` is not present)
* `(...)`
	+ `n:2+!x` generate the sequence `2..n+1`, storing in `n`
	+ `n*/:n` calculate a multiplication table of these values
	+ `(x<)_'` drop values larger than `x` from each row
	+ `r:?,/` flatten, then uniquify the remaining values, storing in `r`
	+ `0,` prepend a 0 (guaranteed to not already be present) to end up returning 1-based indices
* `(#r)^` replace nulls (i.e. prime `x`s) with the count of the list (i.e. the number of non-prime numbers smaller than `x`)
[Answer]
# JavaScript (ES6), ~~67 61~~ 55 bytes
*Saved 6 bytes thanks to @tsh*
```
n=>(g=j=>!g[j]*(j>i)+(n-j&&g(g[j]=j+i>n?++i:j+i)))(i=2)
```
[Try it online!](https://tio.run/##FcjBCoMwDADQX@kumqwzB28OUtl3iIzitCS4VHQM9vXddns8je94TLtsr8byYy4LF@MAiZXDKQ06nkGDoAdrtKoS/IvVS7Dee7n@hIgg3GKZsh15nWnNCQYiuu17/EDX4UjPuAHcL07QcXALiPOuRSTNYlC7GrF8AQ "JavaScript (Node.js) – Try It Online")
### Commented
```
n => (            // n = input
  g =             // g is a recursive function taking:
  j =>            //   j = current number being tested
  !g[j] *         // increment the final result if g[j] is not set
  (j > i) + (     // and j is greater than i (i.e. when testing
                  // multiples of i, we don't count i itself)
    n - j &&      // unless j is equal to n,
    g(            // do a recursive call:
      g[j] =      //   mark j as dropped
      j + i > n ? //   if j + i is beyond n:
        ++i       //     increment i and restart
      :           //   else:
        j + i     //     keep going with j + i
    )             // end of recursive call
  )               //
)(i = 2)          // initial call to g with i = j = 2
```
[Answer]
# [Python](https://www.python.org), 76 bytes
```
f=lambda n,*s,t=2:len({*s})if n in[*s,t]else f(n,*s,*range(t+t,n+1,t),t=t+1)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY3fdJscxJzk1ISFfJ0tIp1SmyNrHJS8zSqtYprNTPTFPIUMvOiQeKxqTnFqQppGmBVWkWJeempGiXaJTp52oY6JZpAfSXahppQM5ULijLzSjSi0zQyNdPyixQygYYoQLQY6SgYGhhoxkKVwpwBAA)
[Answer]
# [Haskell](https://www.haskell.org/), 69 bytes
```
f n=n-n![2..n]
n!(h:t)|n`elem`t=1+n![x|x<-t,x`mod`h>0]|1>0=2+length t
```
[Try it online!](https://tio.run/##LZBNboNADIX3PYUjddEqJBp7/kJVcpEKCaSSEhWmUTsLFtyd2mOkhzB@z59nGPu/72Gatu0GqUmndPig8zm1T@nwMr7l1zV1wzTMXW7wyN6yLu@nXC3d/PPZjVfTrng1DR2nIX3lEfI29/cEDTx@7ynDM8z9A25CRGPazVTAwiIqshW4Il8Uii4VxArqUqApFZKWyAMoAL/3wt6TKGOwVo@MeiQew8hphvYMRc2Q9HB/y3lQZ6zVrJVjMs8Kix8bdbZ884yTPPOczDLPGWU4r7MuKssJS64pvtwVleEuyvSS59rLDuZ5UpavdYffd4jvmBecMkPQXUF2y9@LujOiskuu/gc "Haskell – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 34 bytes
```
Ｎθ≔…·²θη≔ＬηζＷ№ηθ«≔Φη﹪κ⌊ηη≦⊖ζ»Ｉ⁻ζＬη
```
[Try it online!](https://tio.run/##RY7LCsIwEEXX9iuynEBdKLjqSipCwYr4B7EdmmCStnlUqPjtccSis7pczj1MI4VreqFTquwQwzmaGzoYeZHtvVedhco2Ono14VXYDmGbs5HnTP6BE9ouSJDUztQ@pNLIoOyjDSA/NGfPbLXAR6UD@amv@zbqHu6UlFUmGjLwxbyqxbAMDtg4NGgDtl//K7s4RepS@AA0jR7mnP2eoCtS2uzSetJv "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
Ｎθ
```
Input `n`.
```
≔…·²θη
```
Start with the list of integers from `2` to `n`.
```
≔Ｌηζ
```
Store its length as we need to adjust for each prime we remove.
```
Ｗ№ηθ«
```
Repeat while `n` is found in the list.
```
≔Φη﹪κ⌊ηη
```
Remove all multiplies of the lowest prime remaining in the list from the list.
```
≦⊕ζ
```
Since this also removes the prime, don't count it as one of the integers that was dropped.
```
»Ｉ⁻ζＬη
```
Output the number of integers that were dropped.
]