2 detalles sobre los numeros primos

1- nunca un par es primo, si no evaluas pares te ahorras el 50% del proceso
2- el minimo multiplo de un numero nunca es mayor que su raíz, es decir, si desglosamos 100


el punto de confluencia siempre será su raiz, ya desde allí es la misma cuenta invertida, con esto et vas a ahorrar un monton de ciclos, por ejemplo para saber si 1.000.001 es primo solo es necesario probar hasta 1.000, así que son 1.000 ciclos (en este caso solo el 0.1% del trabajo y por ser raíz la eficiencia aumenta con lo grande del numero)... sin embargo calcular la raiz cuadrada es una operacion pesada y debemos velar que esto no consuma el proceso que nos ahorramos, así que lo calculamos en inversión...

por esto antes de hacer un programa es importante investigar todas las teorías y temas asociados...

estos 2 consejos son basicos... con esto para los primos de 1.000.001 solo necesitas 0.05% del trabajo que haría tu código

si metemos allí los multiplos de 3 nos reducimos 15% más y el codigo queda algo como

//nunca haremos primos de negativos y podemos evaluar  primos hasta de 64bit
bool es_primo(long unsigned int num){ 
 
  if(num <= 3){
    return >=2; //1 no es primo
  }
 
  long unsigned int mult;
 
  //si mult es la raiz, mult*mult debe ser el numero
  for(mult = 5;mult*mult < num; mult += 6){ //+=6 porque 6 es multiplo de 3 y 2
    if(num % mult == 0) {
      return false; // no es primo
    }
    if(num+2 % mult == 0) {
      return false; // no es primo
    }
  }
  return false; // llegados a este punto debe ser primo
}

lo hice de mente, espero no tenga errores

Para aligerar aún más las cosas (a expensas de usar más memoria) te diría que fueras guardando los primos encontrados en una lista dinámica y usaras los elementos de esa lista como divisores del número que estás operando. Si llegas al final de ella ( o superas la raíz cuadrada del número), sin que ningún elemento haya sido divisible por el número, has encontrado el siguiente primo y lo incluyes en la cola de la lista. Así te evitas de realizar muchas operaciones.

La razón de esto es que cuando factorizas, si te das cuenta, usas siempre el menor primo.

justamente esto hago

de cabeza evalúa 2 y 3, de allí en más empieza en 5 y evalúa x y x+2, luego avanza 6 es decir va algo como 5;7, 11;13, 17;19, 23;25, 29;31, 37;43