소수 구하기(에라토스테네스의 체)

소수(Prime number)

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 같은 의미로 1과 자기 자신 외에는 약수가 존재하지 않는 수를 말한다.

코딩 테스트에는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제 된다.

소수 구하기 이론

소수를 구하는 대표적인 판별법은 에라토스테네스의 체이다.

에라토스테네스의 체 원리
1. 구하고자 하는 소수의 범위만큼 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2를 반복한 후에 남은 모든 수를 출력한다.

이러면 배열 범위 내의 수들 중에서 소수들만 구할 수 있다.

에라토스테네스의 체를 사용할 때 시간 복잡도

에라토스테네스의 체를 사용할 때 일반적으로 이중 for문을 사용하며로 시간 복잡도가 O(N^2)이라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))이다.
왜냐하면 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하기 때문이다.

백준 1929 소수 구하기

https://www.acmicpc.net/problem/1929

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int M, N;
    cin >> M >> N;
    
    vector<int> v(N + 1);

	for(int i = 2; i <= N; i++)
	{
		v[i] = i;
	}
	//제곱근까지만 탐색한다.
	for(int i = 2; i <= sqrt(N); i++)
	{
		if(v[i] == 0)
			continue;
		for(int j = i + i; j <= N; j = j + i)
		{
			v[j] = 0;
		}
	}
    
	for(int i = M; i <= N; i++)
	{
		if(v[i] == 0)
			continue;
		cout << v[i] << '\n';
	}
}

소수를 구할 때는 바깥 for문의 종료 조건에서 N의 제곱근까지만 탐색한다.
왜냐하면 N의 제곱근이 n일 때 N = a * b를 만족하는 a와 b가 모두 n보다 클 수는 없다. a가 n보다 크다면 b는 n보다 작아야 한다. 즉, N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가진다. 따라서 에라토스테네스의 체로 n 이하의 수의 배수를 모두 제거하면 1부터 N사이의 소수를 구할 수 있다.

백준 1456 거의 소수 구하기

https://www.acmicpc.net/problem/1456

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<bool> arr(10000001, true);
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	long long A, B;
	cin >> A >> B;

	long long answer = 0;

	arr[0] = false;
	arr[1] = false;
	for (long long i = 2; i <= sqrt(10000001); i++)
	{
		if (arr[i] == false)
			continue;
		for (long long j = i + i; j <= 10000001; j += i)
		{
			arr[j] = false;
		}
	}
	
	for (long long i = 2; i <= 10000001; i++)
	{
		if (arr[i] == true)
		{
			//소수라면 제곱수를 카운트한다.
			long long temp = i;

			//비교 중에 long long의 범위를 넘으면 잘못 카운트가 되기 때문에 이렇게 B에서 나눠서 수를 비교한다.
			while ((double)i <= (double)B / (double)temp)
			{
				if ((double)i >= (double)A / (double)temp)
				{
					answer++;
				}
				temp *= i;
			}
		}
	}

	cout << answer;
	
	return 0;
}

이 문제는 몇 번 틀렸다. 틀린 이유는 저 거의 소수를 구하는 부분에서 제곱한 수를 직접 B와 비교를 하게 되면 long long 타입의 표현 범위를 벗어나는 수가 나오면 제대로 카운트를 할 수 없게 된다. 그래서 수의 범위를 벗어나지 않도록 이항 정리를 해주었다. 그러면 범위 안에서 제대로 카운팅이 진행된다.

문제 풀이의 아이디어 자체는 간단했다. 소수를 구하고 소수를 차례로 제곱하면서 A, B의 범위에 그 수가 있는지를 판단하기만 하면 되는 문제였다.
어려웠던 점은 수의 범위를 고려해서 구현을 해야 했다는 점이다.

백준 1747 소수&팰린드롬

https://www.acmicpc.net/problem/1747

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;

int N;

bool isPrime(int data);
bool isParindrom(int data);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;

	int k = N;
	while (true)
	{
		if (isPrime(k) && isParindrom(k))
		{
			break;
		}
			
		k++;
	}

	cout << k;
	
	return 0;
}

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

bool isParindrom(int data)
{
	string str = to_string(data);
	int start = 0;
	int end = str.size() - 1;

	while (start < end)
	{
		if (str[start] == str[end])
		{
			start++;
			end--;
		}
		else
			return false;
	}
	return true;
}

이번에는 에라토스테네스의 체를 쓰지 않아보았다.
한 번 틀렸는데, 소수에서 1을 예외처리 하지 않았기 때문이었다.

문제 해결의 과정은 간단히 소수인지 판단 후 펠린드롬 수인지 투포인터로 확인해서 답을 도출해내었다.

Do it! 알고리즘 코딩테스트 C++편 (김종관, 이지스퍼블리싱)