[BOJ] Level8 : 기본 수학2

Introduction

총 6문제이다
대부분 소수, 소인수분해와 관련된 내용이다

---

5번째 문제를 풀던중 홈페이지 접속이 오류가 났다
자고 일어나서 다시 해봐야겠다…

Body

소수를 구하는데 빠르게 연산하는 방법을 요구하는게 대부분였다.
빠르게 구하는 방법은 두가지가 있는 것 같다.

• 에라토스테네스의 체
• sqrt(n) // 제곱근 이용

제곱근 이용하는 것은 정말 이해가 안 가고…
에라토스테네스의 체는 연속된 숫자의 배열에서 소수가 아닌 수를 빼는 방식으로
배열에 소수만 존재하게 된다.

#define MAX 123456 * 2

int arr[MAX + 1];

int main()
{
	// 소수를 미리 찾아 배열에 저장
	for (int idx = 2; idx <= MAX; idx++)
	{
		arr[idx] = idx;
	}

	for (int i = 2; i * i <= MAX; i++)
	{
		if (arr[i] == 0) { continue; }

		for (int j = i * i; j <= MAX; j += i)
		{
			arr[j] = 0;
		}
	}
}

이렇게만 하면 arr[idx]의 값이 0이 아닌수는 소수이다.

---

Conclusion