소수 구하기

소수(prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

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

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

 

소수를 구하는 여러가지 알고리즘을 짜보고 시간복잡도를 비교해보자

 

첫번째 풀이

bool isprime(int num) {
	int cnt = 0;
	if (num == 2)
		return true;
	for (int i = 2; i < num; i++) {
		//비교연산
		if (num % i == 0)
			cnt++;
	}
	if (cnt == 0)
		return true;
	else
		return false;
}

주어진 수 num을 2부터 num-1의 수로 나누어 나누어지면 소수가아니고 나누어지지 않으면 소수로 판별하는 알고리즘이다.

정수 n이 들어왔을때 n-2번의 비교를 한다.

따라서 시간복잡도는 O(n)이다.

 

 

 

두번재 풀이

bool isprime(int num) {
	int cnt = 0;
	if (num == 2)
		return true;
	for (int i = 2; i * i <= num; i++) {
		//비교연산
		if (num % i == 0)
			cnt++;
	}
	if (cnt == 0)
		return true;
	else
		return false;
}

위에 알고리즘을 개선시킨것으로 2부터 num의 제곱근까지 검사하는 알고리즘입니다.

제곱근 이상의 두 수의 곱으로는 num을 초과하게 된다.

정수 n이 들어왔을때 약√n 번의 비교를 한다.

따라서 시간복잡도는 O(√n)이다.

 

 

3번째 풀이

void isprime(int num) {
	int* artos = new int[num + 1];
	for (int i = 0; i <= num; i++) {
		artos[i] = 0;
	}
	for (int i = 2; i <= num; i++) {
		artos[i] = i;
	}
	for (int i = 2; i * i <= num; i++) {
		if (artos[i] != 0) {
			for (int j = i * i; j <= num; j += i)
				artos[j] = 0;
		}
	}
	
	free(artos);
}

 

위의 알고리즘은 수학자 에레토스테네스가 고안한 소수를 구하는 방법이다.

소수의 배수들을 모두 없애버려 소수만 남게하는 방법이다.

시간복잡도는 O(nloglogn)인데 왠지 모르겠다.