여기에서는 n보다 작은 모든 소수를 효율적인 방법으로 생성하는 방법을 살펴보겠습니다. 이 방법에서는 윌슨의 정리를 사용합니다. 그의 정리에 따르면 숫자 k가 소수이면 ((k - 1)! + 1) mod k는 0이 됩니다. 이 아이디어를 얻기 위해 알고리즘을 살펴보겠습니다.
이 아이디어는 큰 정수를 지원하지 않기 때문에 C나 C++와 같은 언어에서는 직접 작동하지 않습니다. 계승은 큰 수를 생성합니다.
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
위 내용은 흥미로운 해결책은 n보다 작은 모든 소수를 얻는 것입니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!