Categorías
Algorithms Interview

LeetCode – Count Primes (Java)

Cuente el número de números primos menos que un número no negativo, n

Solución Java 1

Esta solución excede el límite de tiempo.

public int countPrimes(int n) {
    n = n-1;
 
    ArrayList<Integer> primes = new ArrayList<Integer>();
 
    if(n<=1) 
        return 0;
    if(n==2)
        return 1;
    if(n==3)
        return 2;
 
    primes.add(2);
    primes.add(3);
 
    for(int i=4; i<=n; i++){
        boolean isPrime = true;
        for(int p: primes){
            int m = i%p;
            if(m==0){
                isPrime = false;
                break;
            }
        }
 
        if(isPrime){
            primes.add(i);
        }
    }
 
    return primes.size();
}

Solución Java 2

Esta solución es la implementación de Tamiz de Eratóstenes.

public int countPrimes(int n) {
	if (n <= 2)
		return 0;
 
	// init an array to track prime numbers
	boolean[] primes = new boolean[n];
	for (int i = 2; i < n; i++)
		primes[i] = true;
 
	for (int i = 2; i <= Math.sqrt(n - 1); i++) {
	// or for (int i = 2; i <= n-1; i++) {
		if (primes[i]) {
			for (int j = i + i; j < n; j += i)
				primes[j] = false;
		}
	}
 
	int count = 0;
	for (int i = 2; i < n; i++) {
		if (primes[i])
			count++;
	}
 
	return count;
}
  LeetCode - Vocales inversas de una cadena (Java)

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *