Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:enteros:criba-de-eratostenes [2017/12/22 01:49]
sebach creado
+++ algoritmos-oia:enteros:criba-de-eratostenes [2017/12/26 19:11] (actual)
sebach ↷ Page moved from algoritmos-oia:criba-de-eratostenes to algoritmos-oia:enteros:criba-de-eratostenes
@@ Línea 28: / Línea 28: @@
     vector<int> primes;
     vector<bool> criba(N+1, true); // empiezan todos como "true", posibles primos
+    criba[0]=false;
+    criba[1]=false;
     for(int i=2; i<=N; i++){
         if(criba[i]){
@@ Línea 48: / Línea 50: @@
 ==== Mejoras ====
-FIXME, j=i*i, ir hasta la raiz y despues nos quedan los primos (O(N))
+Algo que podemos ver por ejemplo en la foto, es que al $6$ lo estamos tachando dos veces, ya que es $3*2$. Veamos que cuando estemos en el $5$, vamos a tachar al $10, 15, 20$ que ya estarán tachados. Veamos que en general, al estar en el número $i$, todos los números $i*2, i*3, ..., i*(i-1)$ estarán tachados, ya que son compuestos y tienen un divisor (en particular un divisor primo) más chico que $i$. Luego, el $for$ de $j$ podemos empezarlo en $i*i$, que éste sea el primer múltiplo de $i$ que miremos.
+A partir de este mejora, podemos pensar entonces que cuando $i*i>N$, el segundo for no haría nada, ya que haríamos $j=i*i$ y la condición de $j \leq N$ se corta sin hacer nada.
+Entonces básicamente, si el $for$ de $i$ lo hacemos hasta la raíz de $N$, todos los valores de la criba que nos quedan sin marcar sabemos que serán primos, ya que no tendrán ningún divisor hasta su raíz (que es menor que la raíz de $N$) y como es sabido, esta es la manera de comprobar que es primo.
+Ahora, si quisiéramos tener en una lista a todos los primos, sí deberíamos seguir el $for$ de $i$ hasta $N$ e ir agregando los valores en donde $criba[i]$ es $true$. Pero si sólo queremos poder consultar rápidamente si un número es primo o no, alcanza con ir hasta la raíz de $N$, sabiendo que los que quedan en $true$ más adelante son primos.
+Podemos ver cómo queda el código con estas mejoras mencionadas:
+<code cpp criba-mejorada.cpp>
+#include<bits/stdc++.h>
+using namespace std;
+int main(){
+    int N;
+    cin>>N;
+    vector<int> primes;
+    vector<bool> criba(N+1, true);
+    criba[0]=false;
+    criba[1]=false;
+    for(int i=2; i*i<=N; i++){
+        if(criba[i]){
+            primes.push_back(i);
+            for(int j=i*i; j<=N; j+=i){ // si se hace el for de i hasta N, tener cuidado con que i*i se pase del límite de int, usar long long
+                criba[j]=false;
+            }
+        }
+    }
+    // criba[i] indica verdadero si i es primo y falso si no
+}
+</code>
+FIXME complejidad
+===== Usar la criba para factorizar =====
+Veamos que en la criba, tenemos una tabla enorme con todos los números hasta el $N$ y sólo guardamos true/false. Qué pasa si guardamos números? Qué números tendría sentido guardar?
+Como lo dice el título de la sección, lo que vamos a hacer es guardar factores del número.
+Por ejemplo, al recorrer el $2$, guardamos un $2$ en las posiciones por las que pasamos:
+{{ :algoritmos-oia:cribaconfactor2.jpg?400 |}}
+Luego, cuando miramos el $3$ (como ya vimos, empezamos desde $3^2$ ya que los múltiplos anteriores ya los vimos):
+{{ :algoritmos-oia:cribaconfactor3.jpg?400 |}}
+Entonces **cómo factorizar un número?**
+Bueno, para factorizar $n$, obtenemos de nuestra criba un factor (primo ya que solo insertamos primos como factores) de $n$, $d$. Luego, habrá que factorizar $n/d$, para el cual obtenemos el valor que tiene guardado en la criba.  Y así sucesivamente hasta llegar al $1$, momento en el cual paramos. Podemos inicializar a todos l
+Veamos cómo queda el código:
+<code cpp criba-para-factorizar.cpp>
+#include<bits/stdc++.h>
+using namespace std;
+int main(){
+    int N;
+    cin>>N;
+    vector<int> criba(N+1, -1);
+    for(long long int i=2; i<=N; i++){
+        if(criba[i]==-1){
+ criba[i]=i;
+            for(long long int j=i*i; j<=N; j+=i){
+                criba[j]=i;
+            }
+        }
+    }
+    for(int i=4; i<=min(N, 20); i++){
+ int valor=i;
+ vector<int> factores;
+ while(valor!=1){
+ factores.push_back(criba[valor]);
+ valor/=criba[valor];
+ }
+ sort(factores.begin(), factores.end());
+ cout<<"Factores de "<<i<<": ";
+ for(int d : factores){
+ cout<<d<<", ";
+ }
+ cout<<endl;
+ }
+}
+</code>

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página