[알고리즘] 소수(Prime Number) 구하기

소수(Prime Number)란

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

소수 (수론) - 위키백과, 우리 모두의 백과사전

---

소수만 구하는 알고리즘

 

풀이1

2부터 n까지 나눠보고 나머지가 0이 안나오게 되면 소수가 되는 방법이다. 이 경우에는 시간 복잡도가 O(n)이 된다.

bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int num = 3;

    if (isPrime(num))
        cout << num << "은 소수 입니다.";
    else
        cout << num << "은 소수가 아닙니다.";
    
	return 0;
}

 

n / 2해도 결과는 같다. 대신 불필요한 연산을 반으로 줄일 수 있다.

 

---

풀이2

2부터 √n까지 나눠 떨어지는 방법을 이용한 알고리즘이다. 이 경우에는 시간 복잡도가 O( √n )이 된다.

bool isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int num = 9;

    if (isPrime(num)) 
        cout << num << "은 소수 입니다.";
    else 
        cout << num << "은 소수가 아닙니다.";
    
	return 0;
}

 

---

풀이3

에라토스테네스의 체 알고리즘을 이용하는 방법이다. 이 방법 같은 경우에는 범위 내에 모든 소수를 찾을 때 유용하다.

시간 복잡도는 O(N * log log N)가 된다.

int main() {
    int n = 9;
    vector<bool> isPrime(n + 1, true);
    
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			for (int j = i * 2; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
    
	return 0;
}

 

n + 1개 만큼 bool형 벡터를 만들어서 소수의 배수가 되는 것들을 지워나가는 방식을 이용한다.

지워 나가는 방식을 알고 싶다면 링크에 들어가면 자세히 알 수 있다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전