[TIL] 05.22 개발일지

📙  공부 한 것

- 백준 알고리즘

  2839 설탕배달

  4948 배르트랑 공준

  2869 달팽이는 올라가고싶다

  10250 ACM 호텔

  1929  소수 구하기

 

🔍 부족한 점

 

1.  소수 구하는 알고리즘 중에 에라토스테네스 체의 알고리즘을 완벽히 체득하지 못했다.

2.  수식적으로 알고리즘문제 푸는  연습이 부족했던 것 같다.

(완전멘붕)

 

💡 알고 가는 것

1부터 120사이의 소수를 구하는 방식은 에라토스테네스 체로 구현한 것이다.

이미 소수로 판정이 된 수의 배수를 제거하는 알고리즘형태이다.

int N = 120; // 소수를 찾을 범위
boolean[] isPrime = new boolean[N + 1]; // 소수 판별을 위한 배열 생성
for (int i = 2; i <= N; i++) {
    isPrime[i] = true; // 일단 모든 수를 소수로 초기화
}
for (int i = 2; i * i <= N; i++) {
    if (isPrime[i]) { // i가 소수인 경우
        for (int j = i * i; j <= N; j += i) {
            isPrime[j] = false; // i의 배수들은 소수가 아님
        }
    }
}
for (int i = 2; i <= N; i++) {
    if (isPrime[i]) { // 해당 수가 소수인 경우
        System.out.print(i + " "); // 출력
    }
}