이 문제에서 우리는 숫자 N이 주어지고 그것이 소수인지 아닌지를 확인하는 것이 우리의 임무입니다.
우선성 테스트 s 주어진 숫자가 소수인지 여부를 확인하는 데 사용되는 알고리즘입니다.
소수는 자기 자신으로만 나눌 수 있는 수입니다. 예 :2, 3, 5, 7.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input: 11 Output: Yes
숫자의 소수성 테스트를 확인하는 방법에는 여러 가지가 있습니다.
소수를 확인하는 한 가지 간단한 방법은 숫자를 N보다 작은 모든 숫자로 나누는 것을 확인하는 것입니다. 임의의 숫자가 N을 나누면 소수가 아닙니다.
모든 i =2 - n-1을 확인합니다. n/i ==0이면 소수가 아닙니다.
이 방법은 알고리즘에서 이러한 작은 변경을 통해 더 효율적으로 만들 수 있습니다.
먼저 n 대신 √n까지 값을 확인해야 합니다. 이것은 많은 루프 값을 저장합니다. √n은 n의 가능한 모든 요인의 값을 포함합니다.
다른 변경 사항은 2와 3으로 나눗셈을 확인하는 것일 수 있습니다. 그런 다음 5에서 √n까지 루프 값을 확인합니다.
이 알고리즘의 구현을 보여주는 프로그램
예시
#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main() {
int n = 341;
if (isPrimeNumber(n))
cout<<n<<" is prime Number.";
else
cout<<n<<" is not prime Number.";
return 0;
} 출력
341 is not prime Number.
숫자의 소수를 확인하는 다른 효과적인 방법은 페르마의 방법을 사용하는 것입니다. 이는 페르마의 작은 정리를 기반으로 합니다.
페르마의 작은 정리 소수 N의 경우 (1, n-1)에 속하는 x의 모든 값. 아래는 사실입니다.
a n-1 ≡ 1 (mod n) or a n-1 % n = 1
이 정리의 구현을 보여주는 프로그램,
예시
#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
int res = 1;
a = a % p;
while (n > 0){
if (n & 1)
res = (res*a) % p;
n = n/2;
a = (a*a) % p;
}
return res;
}
int gcd(int a, int b) {
if(a < b)
return gcd(b, a);
else if(a%b == 0)
return b;
else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
while (k>0){
int a = 2 + rand()%(n-4);
if (gcd(n, a) != 1)
return false;
if (power(a, n-1, n) != 1)
return false;
k--;
}
return true;
}
int main() {
int k = 3, n = 23;
if(isPrime(n, k)){
cout<<n<<" is a prime number";
}
else
cout<<n<<" is not a prime number";
return 0;
} 출력
23 is a prime number