Nuevo algoritmo para generar números primos del 1 al número N

Además del método Tamiz de Eratóstenes para generar números primos, podemos implementar un nuevo algoritmo para generar números primos del 1 al N. Puede ser sorprendente saber que todos los números primos ≥ 5 se pueden rastrear a partir de un patrón: Tratemos de entender la serie:

Serie 1: 5 + 6 = 11 11 + 6 = 17 17 + 6 = 23 23 + 6 = 29 … …

Serie 2: 7 + 6 = 13 13 + 6 = 19 … …

Vemos que sumando 6 a 5 y nuevamente sumando 6 al resultado obtenido, podemos obtener otro número primo. Del mismo modo, sumar 6 a 7 y nuevamente sumar 6 al resultado obtenido. podemos obtener otro número primo. Por lo tanto, podemos inferir que podemos obtener todos los números primos haciendo el mismo procedimiento. Sin embargo, cuando seguimos sumando 6 al resultado anterior para obtener el siguiente número primo, podemos notar algunos números que no son números primos. Por ejemplo:

13 + 6 = 19 (Número primo) 19 + 6 = 25 (Número compuesto; Decir número pseudoprimo) 29 + 6 = 35 (Número compuesto; Decir número pseudoprimo)

Podemos decir estos tipos de Números Compuestos como Números PseudoPrimos (aparecen como números primos, pero no lo son en realidad). Ahora, si somos capaces de separar estos Pseudo Números Primos de los Números Primos Reales, podemos obtener los Números Primos Reales. Usando 4 ecuaciones importantes, podemos rastrear exactamente todos estos Pseudo Números Primos y separarlos de los Números Primos Reales. La Ecuación que generará la serie es:

y = 6 * x ± 1 donde x = 1, 2, 3, 4, 5, 6, 7, … Por ejemplo: 6 * (1) – 1 = 5 (Número primo) 6 * (1) + 1 = 7 (Número primo) 6 * (2) – 1 = 11 (Número primo) 6 * (2) + 1 = 13 (Número primo) 6 * (3) – 1 = 17 (Número primo) 6 * (3) + 1 = 19 (Número primo) 6 * (4) – 1 = 23 (Número primo) 6 * (4) + 1 = 25 (Número pseudoprimo)

Podemos rastrear todos los Pseudo Números Primos usando 4 ecuaciones: Para la serie producida a partir de y = 6 * x – 1:

1. y = (6 * d * x) + d donde, x = {1, 2, 3, 4, 5, 6, …}
2. y = (6 * d * x) + (d * d) donde, x = {0, 1, 2, 3, 4, 5, …} y d = {5, (5+6), (5+6 +6), (5+6+6+6), …, (5+(n-1)*6)}

Para la serie producida a partir de y = 6 * x + 1:

1. y = (6 * d * x) + (d * d) donde, x = {0, 1, 2, 3, …}
2. y = (6 * d * x) + (d * d) – 2 * d donde, x = {1, 2, 3, 4, …}, d = {7, (7+6), (7+6 +6), …, (7 + (n – 1) * 6)} y n = {1, 2, 3, 4, 5, …}

Ejemplos Tome d = 5 y x = 0 en la ecuación 2, y = 25 (pseudo número primo) Tome d = 5 y x = 1 en la ecuación 1, y = 35 (pseudo número primo) De manera similar, poner valores en la ecuación 3 y 4 podemos rastrear todos los números pseudo primos.

¿Cómo implementar en la programación?

Asumimos dos arrays de tipo bool del mismo tamaño. Digamos que el primero es array1 , cada elemento del cual se inicializa en 0 . Y, el segundo es array2 , cada elemento del cual se inicializa en 1 . Ahora, en array1 , inicializamos los índices especificados con 1 , los valores de índice se calculan usando la ecuación y = (6 * x) ± 1 . Y, en array2 , inicializamos los índices especificados con 0 , los valores de índice se calculan usando 4 ecuaciones descritas anteriormente. Ahora, ejecute un bucle de 0 a N e imprima el valor de índice de la array, si array1[i] = 1 yarray2[i] = 1 (i es un número primo).

A continuación se muestra la implementación del enfoque: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of prime numbers <= n
int countPrimesUpto(int n)
{
 
    // To store the count of prime numbers
    int count = 0;
 
    // To mark all the prime numbers according
    // to the equation (y = 6*x -/+ 1)
    // where x = 1, 2, 3, 4, 5, 6, 7, ...
    bool arr1[n + 1];
 
    // To mark all the Pseudo Prime Numbers
    // using the four equations
    // described in the approach
    bool arr2[n + 1];
 
    // Starting with >= 5
    int d = 5;
 
    // 2 and 3 are primes
    arr1[2] = arr2[2] = 1;
    arr1[3] = arr2[3] = 1;
 
    // Initialize every element of arr1 with 0
    memset(arr1, 0, sizeof(arr1));
 
    // Initialize every element of arr2 with 1
    memset(arr2, 1, sizeof(arr2));
 
    // Update arr1[] to mark all the primes
    while (d <= n) {
 
        // For 5, (5 + 6), (5 + 6 + 6), ...
        memset(arr1 + d, 1, (sizeof(arr1)) / (n + 1));
 
        // For 7, (7 + 6), (7 + 6 + 6), ...
        memset(arr1 + (d + 2), 1, (sizeof(arr1)) / (n + 1));
 
        // Increase d by 6
        d = d + 6;
    }
 
    // Update arr2[] to mark all pseudo primes
    for (int i = 5; i * i <= n; i = i + 6) {
        int j = 0;
 
        // We will run while loop until we find all
        // pseudo prime numbers <= n
        while (1) {
            int flag = 0;
 
            // Equation 1
            int temp1 = 6 * i * (j + 1) + i;
 
            // Equation 2
            int temp2 = ((6 * i * j) + i * i);
 
            // Equation 3
            int temp3 = ((6 * (i + 2) * j)
                         + ((i + 2) * (i + 2)));
 
            // Equation 4
            int temp4 = ((6 * (i + 2) * (j + 1))
                         + ((i + 2) * (i + 2)) - 2 * (i + 2));
 
            // If obtained pseudo prime number <=n then its
            // corresponding index in arr2 is set to 0
 
            // Result of equation 1
            if (temp1 <= n) {
                arr2[temp1] = 0;
            }
            else {
                flag++;
            }
 
            // Result of equation 2
            if (temp2 <= n) {
                arr2[temp2] = 0;
            }
            else {
                flag++;
            }
 
            // Result of equation 3
            if (temp3 <= n) {
                arr2[temp3] = 0;
            }
            else {
                flag++;
            }
 
            // Result of equation 4
            if (temp4 <= n) {
                arr2[temp4] = 0;
            }
            else {
                flag++;
            }
 
            if (flag == 4) {
                break;
            }
            j++;
        }
    }
 
    // Include 2
    if (n >= 2)
        count++;
 
    // Include 3
    if (n >= 3)
        count++;
 
    // If arr1[i] = 1 && arr2[i] = 1 then i is prime number
    // i.e. it is a prime which is not a pseudo prime
    for (int p = 5; p <= n; p = p + 6) {
        if (arr2[p] == 1 && arr1[p] == 1)
            count++;
 
        if (arr2[p + 2] == 1 && arr1[p + 2] == 1)
            count++;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int n = 100;
    cout << countPrimesUpto(n);
}

25

Espacio Auxiliar: O(n)