Get list of primes to N

Question

I'm trying to write a function which takes an Int and returns all of the prime numbers up to and including that Int.

for example "list of primes for 8" = List(3,5,7)

This is what I have so far :

  def isPrime(i: Int): Boolean = {
    if (i <= 1)
      false
    else if (i == 2)
      true
    else
      !(2 to (i - 1)).exists(x => i % x == 0)
  }                                               //> isPrime: (i: Int)Boolean

    def getListOfPrimesToN(n : Int) = {

    }

for the function getListOfPrimesToN I plan to 1. create a List "l" of size n and populate it with elements ranging from 0 to n. 2. call map function of "l" and call isPrime for each element in List.

How to create the List of element 1 to N ?

Any alternative solutions for returning all of the prime numbers up to and including an Int N welcome.

Answer 1

You can solve this with infinite streams. If you had a stream primes of all the primes, you could just say primes.takeWhile(_ <= n) to get the primes up to and including n.

To get all the primes, you start with a stream of all the numbers starting from 2, the first prime. You can then skip all the even numbers since those are definitely not prime. Then you can skip all the other numbers that are not prime.

val primes = 2 #:: Stream.from(3,2).filter(isPrime)

Now you just need isPrime to check if a given number is prime. A number is prime if it is not divisible by any smaller prime. We actually need only consider primes whose square is not greater than the number (since, logically, a composite number's smallest prime factor can't be larger than its square root).

def isPrime(n: Int): Boolean =
  primes.takeWhile(p => p*p <= n).forall(n % _ != 0)

Check this in the REPL:

scala> primes.takeWhile(_ <= 8).toList
res0: List[Int] = List(2, 3, 5, 7)

Caveat: This only works for positive numbers smaller than Integer.MAX_VALUE.

Answer 2

An implementation of the Sieve of Eratosthenes algorithm for efficiently finding prime numbers up to a given value N includes the following, (fixed and improved on this SO answer),

implicit class Sieve(val N: Int) extends AnyVal {
  def primesUpTo() = {
    val isPrime = collection.mutable.BitSet(2 to N: _*) -- (4 to N by 2)
    for (p <- 2 +: (3 to Math.sqrt(N).toInt by 2) if isPrime(p)) {
      isPrime --= p*p to N by p
    }
    isPrime.toImmutable
  }
} 

Hence

10.primesUpTo.toList
res: List(2, 3, 5, 7)

11.primesUpTo.toList
res: List(2, 3, 5, 7, 11)

Note Find prime numbers using Scala. Help me to improve for additional ideas and discussion.