numeros_primos.md

Numeros primos

La mayor cantidad de problemas en teoría de números hablan sobre números primos.

definición:

un número primo es un número mayor a 1 que no se puede expresar como a x b, para a y b enteros mayores a 1.

Como verificar que n es un número primo?

Si negamos la definición, podemos ver que si n no es ún número primo, entonces, existen enteros a y b tal que n = a x b.

Luego, sin perdida de generalidad hacemos a <= b y con lo cuál n = a x b >= a x a, y por ultimo podemos afirmar:

Lema 1

si n no es primo, entonces, existe un numero menor o igual a la raiz de n y mayor a 1 que divide a n.

// O(sqrt(n))
bool isPrime(int n) {
  if (n == 1) return false;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false; 
    }
  }
  return true;
}

Criba de Eratostenes

criba

La criba de eratostenes, se basa en la siguiente idea:

un numero primo n no es multiplo de todo numero mayor a 1, que sea menor a n.

bool composite[maxN];
//O(nloglogn)
void sieve(int n) {
  for (int i = 2; i <= n; ++i) {
    if (not composite[i]) {
      for (int j = 2*i; j <= n; j += i) {
        composite[j] = 1;  
      }
    }
  }
}

Como se puede obtener una mejor cota?

El segundo for, se puede iniciar en i * i, esto se debe a que un numero n, diferente de i, que es divisible por i, siendo i primo, tiene que ser por lo menos i * i, para que no sea divisible por algun primo menor a i.

bool composite[maxN];
//O(nloglogn)
void sieve(int n) {
  for (int i = 2; i*i <= n; ++i) {
    if (not composite[i]) {
      for (int j = i*i; j <= n; j += i) {
        composite[j] = 1;
      }
    }
  }
}

Criba en tiempo lineal

criba lineal

La idea principal se basa en que todo numero es unicamente representado por el par (menor primo, numero / (menor primo))

bool composite[maxN];
vector<int> prime;
//O(n)
void sieve(int n) {
  for (int i = 2; i <= n; ++i) {
    if (not composite[i]) {
       prime.push_back(i);
    }
    for (int p : prime) {
      if (p * i > n) break;  
      composite[p * i] = 1;
      if (i % p == 0) break;
    }
  }
}

Mejoras en cota para saber si un numero es primo.

El lema 1, se puede expresar como:

si n no es primo, entonces, existe un numero primo menor o igual a la raiz de n y mayor a 1 que divide a n.

prime number theorem

La cantidad de numeros menores a n es O(n / log (n)).

Funciones multiplicativas

funciones multiplicativas

Una funcion multiplicativa es una funcion aritmetica que cumple:

1. F(1) = 1

2. F(a x b) = F(a) x F(b) si a y b son coprimos