Data Structure & Algorithms
DSA
Introduction to problem solving
Count of Primes

# Count of primes

## Problem Description

You will be given an integer n. You need to return the count of prime numbers less than or equal to n.

### Problem Constraints

``0 <= n <= 10^3``

### Input Format

``Single input parameter n in function.``

### Output Format

``Return the count of prime numbers less than or equal to n.``

### Example Input

``````Input 1:
19

Input 2:
1``````

### Example Output

``````Output 1:
8

Output 2:
0``````

### Example Explanation

``````Explanation 1:
Primes <= 19 are 2, 3, 5, 7, 11, 13, 17, 19

Explanation 2:
There are no primes <= 1 ``````

### Output

Java
``````public class CountPrimes {
public int countPrimes(int n) {
if (n <= 2) {
return 0;
}

boolean[] isPrime = new boolean[n];
int count = 0;

for (int i = 2; i < n; i++) {
if (!isPrime[i]) {
count++;
for (int j = 2; (long)i * j < n; j++) {
isPrime[i * j] = true;
}
}
}
return count;
}

public static void main(String[] args) {
CountPrimes countPrimes = new CountPrimes();
System.out.println(countPrimes.countPrimes(19)); // Output: 8
System.out.println(countPrimes.countPrimes(1));  // Output: 0
}
}``````
Python
``````class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0

is_prime = [True] * n
is_prime[0] = is_prime[1] = False
count = 0

for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
is_prime[i * i: n: i] = [False] * len(is_prime[i * i: n: i])

return sum(is_prime)

sol = Solution()
print(sol.countPrimes(19))  # Output: 8
print(sol.countPrimes(1))   # Output: 0``````
JavaScript
``````function countPrimes(n) {
if (n <= 2) {
return 0;
}

const isPrime = new Array(n).fill(true);
isPrime[0] = isPrime[1] = false;
let count = 0;

for (let i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (let j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}

for (let i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}

return count;
}

console.log(countPrimes(19));  // Output: 8
console.log(countPrimes(1));   // Output: 0``````