n보다 작은 모든 소수를 얻는 흥미로운 솔루션?

여기서는 n보다 작은 모든 소수를 효율적인 방법으로 생성하는 방법을 살펴보겠습니다. 이 접근법에서 우리는 윌슨의 정리를 사용할 것입니다. 그의 정리에 따르면 숫자 k가 소수이면 ((k - 1)! + 1) mod k는 0이 됩니다. 이 아이디어를 얻기 위한 알고리즘을 살펴보겠습니다.

이 아이디어는 큰 정수를 지원하지 않기 때문에 언어와 같은 C 또는 C++에서 직접 작동하지 않습니다. 계승은 많은 수를 생성합니다.

알고리즘

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

예시

#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);
}

출력

2 3 5 7