Dados dos números L y R, la tarea es encontrar los números primos entre L y R.
Ejemplos:
Entrada: L = 1, R = 10
Salida: 2 3 5 7
Explicación:
Los números primos entre el 1 y el 10 son 2, 3, 5 y 7
Entrada: L = 30, R = 40
Salida: 31 37
Enfoque: la idea es iterar desde el rango [L, R] y verificar si algún número en el rango dado es primo o no. En caso afirmativo, imprima ese número y verifique el siguiente número hasta que iteremos todos los números.
Debajo de la implementación del enfoque anterior:
C
// C program to find the prime numbers // between a given interval #include <stdio.h> // Function for print prime // number in given range void primeInRange(int L, int R) { int i, j, flag; // Traverse each number in the // interval with the help of for loop for (i = L; i <= R; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; // Iterate to check if i is prime // or not for (j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) printf("%d ", i); } } // Driver Code int main() { // Given Range int L = 1; int R = 10; // Function Call primeInRange(L, R); return 0; }
C++
// C++ program to find the prime numbers // between a given interval #include <bits/stdc++.h> using namespace std; // Function for print prime // number in given range void primeInRange(int L, int R) { int flag; // Traverse each number in the // interval with the help of for loop for (int i = L; i <= R; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; // Iterate to check if i is prime // or not for (int j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) cout << i << " "; } } // Driver Code int main() { // Given Range int L = 1; int R = 10; // Function Call primeInRange(L, R); return 0; }
2 3 5 7
Complejidad de tiempo: O((RL)*N) , donde N es el número, y L y R son el rango dado.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por divyemaggo69 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA