99클럽 코테 스터디 1일차 TIL - 소수 구하기

Hyejin·2025년 3월 31일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99Club

목록 보기

1/21

문제: https://www.acmicpc.net/problem/1929
알고리즘 분류: 수학 정수론 소수 판정 에라토스테네스의 체

소수 (Prime Number)

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
- 1 이하의 수는 소수가 아니다.
2, 3, 5, 7, 11, 13, 17,...
- 2와 3은 소수이다.
- 소수와 6k±1 형태의 관계 ✅
  - 2보다 큰 모든 소수는, 6으로 나눌 때, 나머지가 1 또는 5 (k는, 0 이상의 정수)
  - 6k+5 형태 (5, 11, 17, 23, ...)
  - 6k+1 형태의 다음 수 (7, 13, 19, 25, ...)

코드 순서

fs 모듈을 이용해 파일 전체를 읽어와 문자열로 저장하기
소수인 지 판별하는 isPrime 함수
M과 N의 범위 안에서 소수 찾는 findPrimesInRange 함수

내 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let line = input[0].split(' ');

let m = Number(line[0]);
let n = Number(line[1]);

findPrimesInRange(m,n);

// 소수인지 판별하는 함수
function isPrime(num){

	if(num <=1) return false; // 1 이하의 정수는 소수가 아니다
	if(num === 2 || num === 3) return true; // 2와 3은 소수이다
	if(num % 2 === 0 || num % 3 === 0) return false; // 2의배수 또는 3의 배수는 소수가 아니다

  	// 6k±1 형태의 관계 고려한 for루프
	for(let i = 5 ; i * i <= num; i += 6){ // 6씩 증가
		if(num % i === 0 || num % (i+2) === 0) return false;
	}
	return true;
}

// 범위 안에서 소수 찾기
function findPrimesInRange(m,n){
	for(let i = m; i <= n; i++){
		if(isPrime(i)){
			console.log(i)
		}
	}
}

추가 설명

for루프에서, i * i <= num 조건을 사용한 이유 ? ➡️ 소수 판별 시 효율성을 높이기 위해서

for (let i = 5; i * i <= num; i += 6) {
  if (num % i === 0 || num % (i + 2) === 0) return false;
}

어떤 숫자가 소수인지 확인하려면 그 숫자가 다른 숫자들로 나누어지는지 확인해야 함
예: 36
36 = 1 × 36
36 = 2 × 18
36 = 3 × 12
36 = 4 × 9
36 = 6 × 6 ------------> 6 × 6을 기준으로, 앞과 뒤의 쌍이 서로 반대로 반복
36 = 9 × 4
36 = 12 × 3
36 = 18 × 2
36 = 36 × 1
핵심 아이디어
이렇게 어떤 숫자의 약수를 찾을 때, 그 숫자의 제곱근(√)까지만 확인하면 모든 가능한 약수 쌍을 발견
또 하나 예시를 들어보면,
100의 제곱근은 10
2부터 10까지만 확인하면 100의 모든 약수 쌍을 발견
만약 이 범위에서 약수가 하나도 없다면, 그 숫자는 소수다!
i * i <= num은 "i가 num의 제곱근보다 작거나 같을 때까지만 반복" 한다는 것
Math.sqrt(num)처럼 직접 제곱근을 계산하는 것보다 i * i <= num 방식이 더 빠르고, 비용이 저렴

내 코드의 성능

메모리: 17220 KB, 시간: 2644 ms
성능을 더 좋게 만들 수 없을 까?

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘

특히 넓은 범위의 소수를 찾을 때 효율적

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let line = input[0].split(' ');

let m = Number(line[0]);
let n = Number(line[1]);

// 에라토스테네스의 체를 사용한 소수 찾기✨
function findPrimesInRange(m, n) {
  // 0부터 n까지의 모든 수가 소수인지 표시하는 배열 (true면 소수)
  let isPrime = Array(n + 1).fill(true);
  
  // 0과 1은 소수가 아님
  isPrime[0] = isPrime[1] = false;
  
  // 에라토스테네스의 체 알고리즘
  // i의 배수들을 모두 소수가 아님으로 표시
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      // i의 배수들을 모두 소수가 아님으로 표시
      // i*i부터 시작하는 이유는 i*2, i*3, ..., i*(i-1)은 이미 이전 단계에서 처리되었기 때문
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  // m부터 n까지의 소수 출력
  for (let i = m; i <= n; i++) {
    if (isPrime[i]) {
      console.log(i);
    }
  }
}

findPrimesInRange(m, n);