소수(Prime Number) 판별 [c++]

Ⅰ. 하나의 숫자가 소수인지 판별

bool isPrimeNumber(int x) { // 어떤 수 x의 "제곱근" 까지만 검사하는 것이 효과적임
int end = (int) sqrt(x);
cout << end;
for (int i = 2; i <= end; i++) {
if (x % i == 0) return false;
}
return true;
}

 

위와같은 코드의 시간 복잡도는 O(N^(1/2)) 이다.

만약 sqrt(x) 값이 아닌 x까지 for문을 돌렸다면 O(N) 으로 비효율적인 알고리즘이 나왔을 것이다.

 

 

 

 

Ⅱ. 대량의 소수를 한꺼번에 판별 (에라토스테네스의 체)

 

1. 배열을 생성하여 값을 초기화 한다.

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다.

 (이때 자기 자신은 지우지 않는다 ex) i=2일때 2는 지우지 않음)

 

#include <iostream>
#include <math.h>

using namespace std;

int arr[100001];

void primeNumberSieve(int x) {
for (int i = 2; i <= x; i++) {
arr[i] = i;
} // 배열에 숫자 삽입
for (int i = 2; i <= x; i++) {
if (arr[i] == 0) continue; // 이미 지워진 숫자인 경우 아래코드 생략
for (int j = i + i; j < x; j += i) { // i를 제외한 i의 배수를 배열에서 지움
arr[j] = 0;
}
}
for (int i = 2; i <= x; i++) {
if (arr[i] != 0) cout << arr[i] << ' ';
}
}


int main() {

// cout << isPrimeNumber(11);
primeNumberSieve(50);
return 0;
}

 

 

Another Code.

 

// 에라토스테네스의 체
#include <string.h>
#include <iostream>

using namespace std;

int* a;

void primeNUMBER(int n) {
for (int i = 2; i <= n; i++) { // 2부터 시작해서
if (a[i]) continue; // 이미 1처리 된 것들은 건너뜀
for (int j = i + i; j <= n; j+=i) { // i를제외한 i의 배수를 1로 바꿈
a[j]++;
}
}
}

int main() {
int n;
cin >> n;
a = new int[n + 1]; // n+1개의 배열 생성
memset(a, 0, sizeof(int)*(n+1));
primeNUMBER(n);

for (int i = 2; i <= n; i++) {
if (!a[i]) cout << i << ' ';
}


return 0;
}