How many Sieve of Eratosthenes hits?

Question

Sieve of Eratosthenes 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, the aim is to have the shortest code(in bytes) possible within the respect of golfing rules.

This is also 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

Answer 1

Ruby, 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!

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 2

05AB1E, 19 bytes

ÅP©÷L€¦®*˜ÙIpigëIk>

Outputs the \$n^{th}\$ term.

Try it online or verify the first 23 test cases or see this for a step-by-step outout.

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 3

Python 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!

Answer 4

Retina 0.8.2, 53 bytes

.+
$*,

$.`$*
^..

+1`(?=.*1$)(,(1+),.*?,)\2+\b
$1#
#

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 5

Jelly, 13 bytes

ḊÆfḢ$ÞẒÐḟ⁸0¦i

A monadic Link that accepts an integer, n, and yields an integer.

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 6

C (gcc), 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!

Inputs an integer \$n\ge 2\$.
Returns the \$n^{\text{th}}\$ term.

Answer 7

Python, 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!

Answer 8

K (ngn/k), 38 34 bytes

-4 bytes by adapting @Kevin Cruijssen's 05AB1E answer

{(#r)^(0,r:?,/(x<)_'n*/:n:2+!x)?x}

Try it online!

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 xs) with the count of the list (i.e. the number of non-prime numbers smaller than x)

Answer 9

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!

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 10

Python, 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!

Answer 11

Haskell, 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!

Answer 12

Charcoal, 34 bytes

Ｎθ≔…·²θη≔ＬηζＷ№ηθ«≔Φη﹪κ⌊ηη≦⊖ζ»Ｉ⁻ζＬη

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.