An interesting solution to get all prime numbers smaller than n
This approach is based on Wilson’s theorem and uses the fact that factorial computation can be done easily using DP
Wilson’s theorem says if a number k is prime then ((k-1)! + 1) % k must be 0.
Below is a Python implementation of the approach. Note that the solution works in Python because Python supports large integers by default therefore factorial of large numbers can be computed.
C++
// 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
// 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
# 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#
// 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 // 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 ?> |
Javascript
<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> |
Output :
2 3 5 7 11 13
Time Complexity: O(n)
Auxiliary Space: O(1)