Return to Answer

func eratosthenesSieve(to n: Int) -> [Int] {
 var composite = Array(repeating: false, count: n + 1) // The sieve
 var primes: [Int] = []
 if n >= 55 {
 // Upper bound for the number of primes up to and including `n`,
 // from https://en.wikipedia.org/wiki/Prime_number_theorem#Non-asymptotic_bounds_on_the_prime-counting_function :
 let d = Double(n)
 let upperBound = Int(d / (log(d) - 4))
 primes.reserveCapacity(upperBound)
 }
 let squareRootN = Int(Double(n).squareRoot())
 var p = 2
 while p <= squareRootN {
 if !composite[p] {
 primes.append(p)
 for q in stride(from: p * p, through: n, by: p) {
 composite[q] = true
 }
 }
 p += 1
 }
 while p <= n {
 if !composite[p] {
 primes.append(p)
 }
 p += 1
 }
 return primes
}

func eratosthenesSieve(to n: Int) -> [Int] {
 var composite = Array(repeating: false, count: n + 1) // The sieve
 var primes: [Int] = []
 if n >= 150 {
 // Upper bound for the number of primes up to and including `n`,
 // from https://en.wikipedia.org/wiki/Prime_number_theorem#Non-asymptotic_bounds_on_the_prime-counting_function :
 let d = Double(n)
 let upperBound = Int(d / (log(d) - 4))
 primes.reserveCapacity(upperBound)
 } else {
 primes.reserveCapacity(n)
 }
 let squareRootN = Int(Double(n).squareRoot())
 var p = 2
 while p <= squareRootN {
 if !composite[p] {
 primes.append(p)
 for q in stride(from: p * p, through: n, by: p) {
 composite[q] = true
 }
 }
 p += 1
 }
 while p <= n {
 if !composite[p] {
 primes.append(p)
 }
 p += 1
 }
 return primes
}

and marks these as composite. Note that are far less values to compute.

and marks these as composite. Note that there are far less values to compute.

The function – as I would understand the parameter to parameter – computes all primes up to and including n. On the other hand, stride(from: 3, to: n, by: 2) does not include the upper bound, and that is easily verified with

/// Compute list of primes
///
/// - Parameter n: The upper bound
/// - Returns: An array with all primes <= `n`
func generatePrimes(to n: Int) -> [Int] {
 
 if n <= 5 {
 return [2, 3, 5].filter { 0ドル <= n }
 }
 
 var arr = Array(stride(from: 3, through: n, by: 2))
 
 let squareRootN = Int(Double(n).squareRoot())
 for index in 0... {
 if arr[index] > squareRootN { break }
 let num : Int = arr.remove(at: index)
 arr = arr.filter { 0ドル % num != 0 }
 arr.insert(num, at: index)
 }
 
 arr.insert(2, at: 0)
 return arr
}

On a 1.2 GHz Intel Core m5 MacBook (Retina, 12-inch, Early 2016) with 8GM RAM I get the following results:

original 9592 primes up to 100000 time: 0.038
original 78498 primes up to 1000000 time: 0.418
original 664579 primes up to 10000000 time: 9.739
eratosthenes 9592 primes up to 100000 time: 0.001
eratosthenes 78498 primes up to 1000000 time: 0.007
eratosthenes 664579 primes up to 10000000 time: 0.096
eratosthenes 5761455 primes up to 100000000 time: 1.223
eratosthenes 50847534 primes up to 1000000000 time: 15.034

The function – as I understand the to parameter – computes all primes up to and including n. On the other hand, stride(from: 3, to: n, by: 2) does not include the upper bound, and that is easily verified with

/// Compute list of primes
///
/// - Parameter n: The upper bound
/// - Returns: An array with all primes <= `n`
func generatePrimes(to n: Int) -> [Int] {
 
 if n <= 5 {
 return [2, 3, 5].filter { 0ドル <= n }
 }
 
 var arr = Array(stride(from: 3, through: n, by: 2))
 
 let squareRootN = Int(Double(n).squareRoot())
 for index in 0... {
 if arr[index] > squareRootN { break }
 let num = arr.remove(at: index)
 arr = arr.filter { 0ドル % num != 0 }
 arr.insert(num, at: index)
 }
 
 arr.insert(2, at: 0)
 return arr
}

On a 1.2 GHz Intel Core m5 MacBook (Retina, 12-inch, Early 2016) with 8GM RAM I get the following results (slightly reformatted to increase the legibility):

original 9592 primes up to 100000 time: 0.038
original 78498 primes up to 1000000 time: 0.418
original 664579 primes up to 10000000 time: 9.739
eratosthenes 9592 primes up to 100000 time: 0.001
eratosthenes 78498 primes up to 1000000 time: 0.007
eratosthenes 664579 primes up to 10000000 time: 0.096
eratosthenes 5761455 primes up to 100000000 time: 1.223
eratosthenes 50847534 primes up to 1000000000 time: 15.034

This can surely be further improved, a first step would be to handle the case p=2 separately and to use the sieve only for odd numbers (which however complicates the index calculations a bit).

But, as you see, computing the primes up to 1 billion is feasible with the sieve of Eratosthenes (and the numbers are correct, you can compare them with https://primes.utm.edu/howmany.html ).

Going for the trillion

You were also thinking of computing all primes up to one trillion. That might be a problem, no matter which algorithm you choose. According to https://primes.utm.edu/howmany.html , there are 37,607,912,018 prime numbers below 1 trillion. Even if we use 32-bit bit integers to save space, that would still require approx 140 GB memory, which makes returning an array with all that numbers difficult.

So that would require a different approach which allows to compute prime numbers in some given range, instead of all prime numbers up to a limit.