Count Primes

Medium Numbers

Count the number of prime numbers less than n using the Sieve of Eratosthenes.

Sample input

Sample output

Solution

def count_primes(n):
    if n < 2:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n, i):
                is_prime[j] = False
    return sum(is_prime)

print(count_primes(10))

function countPrimes(n) {
  if (n < 2) return 0;
  const isPrime = new Array(n).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i < n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j < n; j += i) isPrime[j] = false;
    }
  }
  return isPrime.filter(Boolean).length;
}

console.log(countPrimes(10));

import java.util.Arrays;

public class Main {
    static int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; (long) i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) isPrime[j] = false;
            }
        }
        int count = 0;
        for (boolean p : isPrime) if (p) count++;
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countPrimes(10));
    }
}

fun countPrimes(n: Int): Int {
    if (n < 2) return 0
    val isPrime = BooleanArray(n) { true }
    isPrime[0] = false
    isPrime[1] = false
    var i = 2
    while (i * i < n) {
        if (isPrime[i]) {
            var j = i * i
            while (j < n) {
                isPrime[j] = false
                j += i
            }
        }
        i++
    }
    return isPrime.count { it }
}

fun main() {
    println(countPrimes(10))
}

func countPrimes(_ n: Int) -> Int {
    if n < 2 { return 0 }
    var isPrime = [Bool](repeating: true, count: n)
    isPrime[0] = false
    isPrime[1] = false
    var i = 2
    while i * i < n {
        if isPrime[i] {
            var j = i * i
            while j < n {
                isPrime[j] = false
                j += i
            }
        }
        i += 1
    }
    return isPrime.filter { $0 }.count
}

print(countPrimes(10))

int countPrimes(int n) {
  if (n < 2) return 0;
  final isPrime = List.filled(n, true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (var i = 2; i * i < n; i++) {
    if (isPrime[i]) {
      for (var j = i * i; j < n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime.where((p) => p).length;
}

void main() {
  print(countPrimes(10));
}

#include <iostream>
#include <vector>
using namespace std;

int countPrimes(int n) {
    if (n < 2) return 0;
    vector<bool> isPrime(n, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long) i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) isPrime[j] = false;
        }
    }
    int count = 0;
    for (bool p : isPrime) if (p) count++;
    return count;
}

int main() {
    cout << countPrimes(10) << endl;
    return 0;
}

#include <stdio.h>

int countPrimes(int n) {
    if (n < 2) return 0;
    int isPrime[1000];
    for (int i = 0; i < n; i++) isPrime[i] = 1;
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; (long long) i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) isPrime[j] = 0;
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++) if (isPrime[i]) count++;
    return count;
}

int main() {
    printf("%d\n", countPrimes(10));
    return 0;
}