¿Cómo podría obtener los números primos entre un rango de (1) a (n) en la raíz cuadrada de N?

Answer 1

Estaba discutiendo un algoritmo para encontrar números primos aquí:

Respuesta de Carlos Eugenio Thompson Pinzón a Busco un programa que me permite calcular numeros primos por ejemplo del 1 al billon ¿alguien sabe?

Un resumen:

1. El primer enfoque: prueba todos sus números [matemática] k [/ matemática] desde [matemática] 1 [/ matemática] a [matemática] n [/ matemática], si es primo. Para verificar si un número es primo, marque [matemática] d [/ matemática] de [matemática] 2 [/ matemática] a [matemática] k-1 [/ matemática], que ninguno de ellos divide [matemática] k [/ matemáticas].
2. Comience a optimizar: solo marque impar [matemática] k [/ matemática] de 3 a [matemática] n [/ matemática]. Marque solo d impar, de [matemática] 3 [/ matemática] a [matemática] \ frac12k [/ matemática]. Aún mejor, de 3 a [matemáticas] \ sqrt k [/ matemáticas].
3. Una mejor optimización, haga una lista de los números primos encontrados y luego verifique cada nueva [matemática] k [/ matemática] con esos números en la lista.
4. Si [math] n [/ math] es demasiado grande y tiene problemas de memoria, solo enumere los números primos menores que [math] \ sqrt n [/ math].

¿Por qué [math] \ sqrt n [/ math] y [math] \ sqrt k [/ math]? si k tiene un divisor [math] d [/ math] como [math] \ sqrt k \ le d <k [/ math], entonces [math] \ frac kd [/ math] también es un divisor de [math] k [/ math] y [math] 1 <\ frac kd \ le \ sqrt k [/ math]. Si [math] \ frac kd [/ math] no es primo, tiene un factor primo que es más pequeño que sí mismo, y por lo tanto más pequeño que [math] \ sqrt k [/ math]. Entonces, el primer primo que divide [math] k [/ math], es menor que [math] \ sqrt k [/ math], a menos que [math] k [/ math] sea primo.

Para cualquier [matemática] k [/ matemática] mayor que [matemática] \ sqrt n [/ matemática]: [matemática] \ sqrt n <k \ le n [/ matemática], solo verificará primos menores que [matemática] \ sqrt k \ le \ sqrt n [/ math], por lo que no es necesario mantener en la memoria ningún primo después de [math] \ sqrt n [/ math].

#include
#include
#include
#include
#define BUFFER_SIZE 72400

int32_t prepara [BUFFER_SIZE];
int max_idx = 0;

int is_prime (int64_t n)
{
int i;
int32_t root = (int32_t) sqrt ((double) n);
para (i = 0; i <max_idx && primes [i] <= root; i ++)
{
if (n% (int64_t) prepara [i] == 0) devuelve 0;
}
if (max_idx <BUFFER_SIZE)
{
primos [max_idx] = n;
max_idx ++;
}
retorno 1;
}

vacío principal()
{
int64_t n;
int c = 0;
printf (“Primes antes de cien millones son: \ n”);
para (n = 2; n <100000000l; n ++)
{
if (es_prime (n))
{
printf (“% 8ld \ n”, n);
c ++;
}
}
printf (“Hay% d números primos. \ n”, c);
}

El tamaño del búfer de 72400 es suficiente para almacenar todos los primos de menos de 1 millón.

El programa fue escrito en C para hacer evidentes problemas de memoria que surgen cuando [math] n [/ math] es demasiado grande.

Answer 2

Puede que me falte algo aquí, pero cualquier algoritmo no perverso para encontrar los números primos en un rango de 1 a n debería ejecutarse en tiempo sqrt (n) o más rápido. La razón es que si un número menor o igual a n no tiene factores primos menores o iguales que sqrt (n), entonces es primo.

Answer 3

Escribe todos los números del 2 al n.

Luego marque 2 y tache cada multiplicado de la lista.

Luego, siempre tome la mayoría del número no marcado a la izquierda (en el siguiente paso es 3) márquelo y tache sus múltiplos que aún no se tachan.

Luego repita esto hasta que el número más grande no marcado sea mayor que sqrt n.

Este método se llama el tamiz de Eratóstenes.

Entonces tienes una lista de primos más pequeños iguales n.

Para obtener los factores primos para algunos N <= 2p donde p es el primo más grande que encontró, solo vea si es divisible a través de cualquier primo en su lista, si no, si ha encontrado otro primo, si es así, divídalo entre este primo (lo haría prueba el más grande primero) si el resultado está en la lista que has terminado si no repites.

Answer 4

O descubres un algoritmo o lo buscas en un libro de referencia.