📚 목차

요약

1. 에라토스테네스의 체 원리

1. 2는 소수이다. 따라서 2의 배수는 소수가 아니다.
2. 3은 소수이다. 따라서 3의 배수는 소수가 아니다.
3. 4는 1번에서 소수에서 배제됐다.
4. 5는 소수이다. 따라서 5의 배수는 소수가 아니다.

…

의 과정을 거쳐서 소수를 걸러내는 방법이다.

bool IsPrimeArray[N+1];

	for (int i = 2; i <= N; i++)
	{
		IsPrimeArray[i] = true; // 일단 모든 수가 소수라고 초기화
	}
	IsPrimeArray[0] = false; // 0과 1은 소수가 아님
	IsPrimeArray[1] = false;

	for (int i = 2; i * i <= N; i++)
	{
		if (IsPrimeArray[i]) // 소수라면 (true라면)
		{
			for (int j = i*i; j <= N; j += i) //해당 수의 배수들은
			{
				IsPrimeArray[j] = false; // 소수가 아니다.
			}
		}
	}

2. 에라토스테네스의 체 시간 복잡도

• 이중 for문을 돌지만 생략되는 loop문이 많아서 실제로는 O(Nlog(logN))이다.

2. 문제 풀어보기