commit c171ba9cee52d0fee96fe60e4175a21782434dd8
parent 9cbd47d9a6db75519e59e3e741679c659077978d
Author: mjkloeckner <martinjkloeckner@gmail.com>
Date: Sat, 16 Mar 2024 22:17:37 -0300
Changed main algorithm of finding prime numbers
The nuew algorithm is the Sieve of Eratosthenes which is a much faster
algorithm than the previously used
Diffstat:
| M | tps/1/main.cpp | | | 50 | +++++++++++++++++++++++++------------------------- |
1 file changed, 25 insertions(+), 25 deletions(-)
diff --git a/tps/1/main.cpp b/tps/1/main.cpp
@@ -2,55 +2,55 @@
#include <fstream>
#include <ctime>
#include <iomanip>
-#include <string>
+#include <vector>
+#include <cmath>
-const unsigned int MAXIMO = 50000;
-
-bool isPrime (long n) {
- if (n <= 1) {
- return false;
- }
-
- for (long i = 2; i < n; ++i) {
- if (!(n % i)) {
- return false;
- }
- }
-
- return true;
-}
+#define OUTPUT_FILE_PATH "primos.txt"
+const unsigned int MAXIMO = 100000000;
int main (void) {
unsigned int ti, tf;
double tt;
std::ofstream fp;
- fp.open("primos.txt");
+ ti = clock();
+
+ unsigned long i, j;
+ std::vector<bool> numeros(MAXIMO);
+ std::fill(numeros.begin(), numeros.end(), true);
+ for (i = 2; i < std::sqrt(MAXIMO); ++i) {
+ if(numeros[i] == true) {
+ for (j = i; j <= (MAXIMO/i); ++j)
+ numeros[i*j] = false;
+ }
+ }
+
+ fp.open(OUTPUT_FILE_PATH);
if (!fp.is_open()) {
- std::cerr << "Unable to open file";
+ std::cerr << "ERROR: No se pudo abrir `" OUTPUT_FILE_PATH << "`";
return -1;
}
- ti = clock();
- unsigned long i, j;
- for (i = j = 0; i < MAXIMO; ++i) {
- if (isPrime(i)) {
+ for (i = 2, j = 0; i < numeros.size(); ++i) {
+ if(numeros[i]) {
fp << i << std::endl;
j++;
}
}
+
+ fp.close();
+
tf = clock();
tt = (double(tf - ti)) / CLOCKS_PER_SEC;
- fp.close();
-
+ std::cout.precision(2);
std::string t_unit = "segundos";
if(tt < 1) {
tt *= 1000;
t_unit.assign("ms");
+ std::cout.precision(0);
}
- std::cout.precision(2);
std::cout << std::fixed
<< "Se econtraron `" << j
<< "` numeros primos en `"
