An interesting solution would be to get all prime numbers less than n?

Here we will see how to generate all prime numbers less than n in an efficient way. In this method we will use Wilson's theorem. According to his theorem, if a number k is a prime number, then ((k - 1)! 1) mod k will be 0. Let's look at the algorithm to get this idea.

This idea won't work directly in a language like C or C because it doesn't support large integers. Factorial produces large numbers.

Algorithm

genAllPrime(n)

Begin
   fact := 1
   for i in range 2 to n-1, do
      fact := fact * (i - 1)
      if (fact + 1) mod i is 0, then
         print i
      end if
   done
End

Example

’s Chinese translation is:

Example

#include <iostream>
using namespace std;
void genAllPrimes(int n){
   int fact = 1;
   for(int i=2;i<n;i++){
      fact = fact * (i - 1);
      if ((fact + 1) % i == 0){
         cout<< i << " ";
      }
   }
}
int main() {
   int n = 10;
   genAllPrimes(n);
}

Output

2 3 5 7

The above is the detailed content of An interesting solution would be to get all prime numbers less than n?. For more information, please follow other related articles on the PHP Chinese website!