meta data for this page
  •  

Count Primes

Leetcode

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1: 

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution 1

Solution 1

public int countPrimes(int n) {
  int count = 0;
  while (n-- > 0) {
    if (isPrime(n)) {
      count++;
    }
  }
  return count;
}
 
private static boolean isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}