[알고리즘] 정수론 : 소수(Prime number) 구하기

📌 소수(Prime Number)란?

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

• 예) 2, 3, 5, 7, 11, 13, ...

 

📌  소수 구하기의 핵심 이론✨

💡에라토스테네스의 체 원리

소수를 구할 때 가장 널리 사용되는 알고리즘! 빠르고 효율적으로 소수를 찾을 수 있다. 🌟

 

1️⃣ 구하고자 하는 소수의 범위만큼 1차원 배열 생성

• 배열의 각 값을 "소수인지 아닌지"를 나타내는 플래그로 사용한다.
• 예를 들어, true면 소수, false면 소수가 아니다.

2️⃣ 2부터 시작해서, 현재 숫자가 소수일 때, 그 배수들을 모두 제거

• 배수는 소수가 될 수 없으므로 지워준다.
• 단, 처음 선택한 숫자는 지우지 않음!

3️⃣ 다음 숫자로 이동해 2️⃣를 반복

• 이미 지워진 숫자는 건너뛰고, 소수인 숫자에 대해 배수를 지운다.

4️⃣ 배열 끝까지 진행 후, 남아 있는 숫자를 출력

• 제거되지 않은 숫자들은 모두 소수이다. 🎉

 

🤓 Example: 에라토스테네스의 체 적용하기

1️⃣ 주어진 범위의 배열 생성

• 1~30까지의 배열을 만든다.
• 1은 소수가 아니므로 제외하고, 2부터 시작한다.

2️⃣ 선택한 수의 배수 삭제

• 현재 숫자 2를 선택하고, 2의 배수를 모두 지웁니다.
  • 예: 4, 6, 8, 10, ...

3️⃣ 다음 숫자 선택

• 다음 소수 3을 선택합니다.
• 3의 배수를 모두 지웁니다.
  • 예: 6, 9, 12, ...

4️⃣ 이 과정을 반복

• 5, 7, 11, 13, ... 등 지워지지 않은 숫자를 선택하며 진행합니다.

5️⃣ 삭제되지 않은 숫자 출력

• 결과적으로 남는 숫자는 모두 소수!
  • 예: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

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

 

• 일반적으로 이중 for문을 사용하므로 O(N²)처럼 보일 수 있음.
• 하지만 실제로는 배수 삭제 과정에서 불필요한 반복을 건너뛰기 때문에 시간 복잡도는 O(N log(log N)).
• 효율적인 배수 삭제 덕분에 소수 구하기의 대표적인 알고리즘으로 사용됨.

 

 

🚫  주의할 점

• 1은 소수가 아니다!
  항상 배열을 초기화할 때 1을 제외해야 한다.
• 범위가 크면 메모리 관리
  소수 범위가 크면 배열 크기도 커지므로 메모리를 신경 써야 한다.
  예: boolean 배열을 사용하거나, 필요한 범위만 계산하도록 설계.
• 시간 최적화 고려
  소수의 배수를 지울 때, 배수 탐색을 시작하는 범위를 최적화하면 성능이 더 좋아질 수 있다.
  • 예: i * i부터 시작해도 충분합니다.

 

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!