Una solución interesante para obtener todos los números primos menores que n

Este enfoque se basa en el teorema de Wilson y utiliza el hecho de que el cálculo factorial se puede hacer fácilmente usando DP El 
teorema de Wilson dice que si un número k es primo, entonces ((k-1)! + 1) % k debe ser 0.
A continuación se muestra la implementación de Python del enfoque Tenga en cuenta que la solución funciona en Python porque Python admite números enteros grandes de forma predeterminada, por lo que se puede calcular el factorial de números grandes. 
 

// C++ program to Prints prime numbers smaller than n
#include<bits/stdc++.h>
using namespace std;
void primesInRange(int n)
{
    // Compute factorials and apply Wilson's
    // theorem.
    int fact = 1;
    for(int k=2;k<n;k++){
        fact = fact * (k - 1);
        if ((fact + 1) % k == 0)
            cout<<k<<endl;
            }
}
 
// Driver code
int main()
{
    int n = 15;
    primesInRange(n);
 
}
// This code is contributed by Rajput-Ji

// Java program prints prime numbers smaller than n
class GFG{
static void primesInRange(int n)
{
    // Compute factorials and apply Wilson's
    // theorem.
    int fact = 1;
    for(int k=2;k<n;k++){
        fact = fact * (k - 1);
        if ((fact + 1) % k == 0)
            System.out.println(k);
            }
}
 
// Driver code
public static void main(String[] args){
int n = 15;
primesInRange(n);
}
}
// This code is contributed by mits

# Python3 program to prints prime numbers smaller than n
def primesInRange(n) :
 
    # Compute factorials and apply Wilson's
    # theorem.
    fact = 1
    for k in range(2, n):
        fact = fact * (k - 1)
        if ((fact + 1) % k == 0):
            print k
 
# Driver code
n = 15
primesInRange(n)

// C# program prints prime numbers smaller than n
class GFG{
static void primesInRange(int n)
{
    // Compute factorials and apply Wilson's
    // theorem.
    int fact = 1;
    for(int k=2;k<n;k++){
        fact = fact * (k - 1);
        if ((fact + 1) % k == 0)
            System.Console.WriteLine(k);
            }
}
 
// Driver code
static void Main(){
int n = 15;
primesInRange(n);
}
}
// This code is contributed by mits

<?php
// PHP program to prints prime numbers smaller than n
function primesInRange($n)
{
    // Compute factorials and apply Wilson's
    // theorem.
    $fact = 1;
    for($k=2;$k<$n;$k++){
        $fact = $fact * ($k - 1);
        if (($fact + 1) % $k == 0)
            print($k."\n");
            }
}
 
// Driver code
$n = 15;
primesInRange($n);
 
// This code is contributed by mits
?>

<script>
// Javascript program to prints prime numbers smaller than n
function primesInRange(n)
{
    // Compute factorials and apply Wilson's
    // theorem.
    let fact = 1;
    for(let k = 2; k < n; k++){
        fact = fact * (k - 1);
        if ((fact + 1) % k == 0)
            document.write((k + "<br>"));
            }
}
 
// Driver code
let n = 15;
primesInRange(n);
 
// This code is contributed by _saurabh_jaiswal
</script>

Producción : 

2
3
5
7
11
13

Este artículo es una contribución de Parikshit Mukherjee . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.