22
\$\begingroup\$

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

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

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ How do I determine whether a number is prime? \$\endgroup\$
    – allxy
    Apr 6 at 8:44
  • \$\begingroup\$ @allxy \$n\$ is prime if you've sieved all the numbers \$2 \dots n-1\$ and \$n\$ hasn't been dropped. \$\endgroup\$
    – Noodle9
    Apr 6 at 9:32
  • 3
    \$\begingroup\$ Another way to determine primality is if n has not been dropped after sieving on all primes <= sqrt(n) \$\endgroup\$
    – Zaelin Goodman
    Apr 6 at 12:14
  • 3
    \$\begingroup\$ Obligatory mention of the "unfaithful" functional sieve cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf \$\endgroup\$
    – qwr
    Apr 7 at 3:54
  • 2
    \$\begingroup\$ I wonder if prime factorizing the number then comparing would improve length/speed of code? (maybe something like Mathematica?) \$\endgroup\$
    – Capercailie
    Apr 7 at 14:38

12 Answers 12

Reset to default
8
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Ohhh... and of course, n is "composite" if it's divisible by itself. Very clever! \$\endgroup\$
    – allxy
    Apr 6 at 9:58
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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 #.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ n=>(g=j=>!g[j]*(j>i)+(n-j&&g(g[j]=j+i>n?++i:j+i)))(i=2) \$\endgroup\$
    – tsh
    Apr 7 at 4:51
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Unlike most code golf answers, this is both small and legible. +1. In other news: Nice. \$\endgroup\$
    – The Daleks
    Apr 8 at 23:56
  • \$\begingroup\$ @The Daleks thanks! I really love the way Haskell codes are so much descriptive \$\endgroup\$
    – AZTECCO
    Apr 9 at 8:51
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.