[알고리즘] 소수 찾기 문제

1.

class Solution {
    public int solution(int n) {
        int answer = 0;
        // for 2 ~ n
        // i가 소수인지 아닌지 판단
        for(int i = 2; i <= n; i++){
            if(i == 2){
                answer += 1;
                continue;
            }
            if (i%2 == 0) continue;
            if (i/2 <= 2){
                answer += 1;
                continue;
            }
            for(int j = 2; j <= i/2; j++){
                if(i%j == 0){
                    break;
                }
                if(j == i/2){
                    answer += 1;
                }
            }
        }
        return answer;
    }
}

 

테스트 1 〉	통과 (0.02ms, 73.5MB)
테스트 2 〉	통과 (0.10ms, 71.8MB)
테스트 3 〉	통과 (0.45ms, 82.2MB)
테스트 4 〉	통과 (1.36ms, 78.9MB)
테스트 5 〉	통과 (0.73ms, 75.4MB)
테스트 6 〉	통과 (11.28ms, 86MB)
테스트 7 〉	통과 (5.58ms, 76.5MB)
테스트 8 〉	통과 (12.41ms, 76.8MB)
테스트 9 〉	통과 (24.72ms, 90MB)
테스트 10 〉	통과 (6926.70ms, 92.3MB)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	통과 (8941.04ms, 80.8MB)

효율성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

채점 결과

정확성: 68.8

효율성: 0.0

합계: 68.8 / 100.0

 

 

효율성이 그냥 없길래 아예 다른 방향으로 생각해보기로 함.

import java.util.*;

class Solution {
    public int solution(int n) {
        
        // 2~n 까지의 수를 자료구조에 담기.
        // 2~n/2까지 돌면서 해당 숫자의 배수를 n에서 제거
        // 예를 들어, 처음에 n에 2가 들어있으니까(==true), 자료구조에서 2의 배수 싹 지움(false)
        // 그 뒤에 3의 배수 싹 지움(본인 제외)
        // ,,, 뒤에 자료구조에 남아있는 가장 작은 수를 기준으로 배수 지우기
        // 남은 거 세기
        
        int answer = 0;
        // 사용할 자료구조: boolean 타입의 배열
        boolean[] prime = new boolean[n+1];
        
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        
        for(int i = 2; i <= n/2; i++){
            if(prime[i]){
                for (int j = 2; i * j <= n; j++) {
                    int tmp = i * j; // 매번 곱셈 발생
                    prime[tmp] = false;
                }
            }
        }
        
        for(int i = 2; i <= n; i++){
            if(prime[i] == true) answer++;
        }
        
        return answer;
        
    }
}

정확성 테스트

테스트 1 〉	통과 (0.03ms, 79.5MB)
테스트 2 〉	통과 (0.04ms, 78.5MB)
테스트 3 〉	통과 (0.05ms, 86.2MB)
테스트 4 〉	통과 (0.12ms, 85.4MB)
테스트 5 〉	통과 (0.07ms, 79MB)
테스트 6 〉	통과 (0.66ms, 71MB)
테스트 7 〉	통과 (0.20ms, 83.3MB)
테스트 8 〉	통과 (0.44ms, 87MB)
테스트 9 〉	통과 (0.99ms, 81.9MB)
테스트 10 〉	통과 (12.19ms, 77.9MB)
테스트 11 〉	통과 (27.39ms, 84.6MB)
테스트 12 〉	통과 (16.26ms, 81.7MB)

효율성 테스트

테스트 1 〉	통과 (26.07ms, 55.1MB)
테스트 2 〉	통과 (28.29ms, 55MB)
테스트 3 〉	통과 (32.12ms, 54.8MB)
테스트 4 〉	통과 (28.77ms, 55.5MB)

 

 

이렇게 해서 맞긴 했는데, 제미나이한테 물어보니, 저기에서 매번 곱셈이 발생하는 것보다 그냥 더하기로 연산하는 게 더 성능이 좋다고 하길래 비교해봄

 

import java.util.*;

class Solution {
    public int solution(int n) {
        
        // 2~n 까지의 수를 자료구조에 담기.
        // 2~n/2까지 돌면서 해당 숫자의 배수를 n에서 제거
        // 예를 들어, 처음에 n에 2가 들어있으니까(==true), 자료구조에서 2의 배수 싹 지움(false)
        // 그 뒤에 3의 배수 싹 지움(본인 제외)
        // ,,, 뒤에 자료구조에 남아있는 가장 작은 수를 기준으로 배수 지우기
        // 남은 거 세기
        
        int answer = 0;
        // 사용할 자료구조: boolean 타입의 배열
        boolean[] prime = new boolean[n+1];
        
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        
        for(int i = 2; i <= n/2; i++){
            if(prime[i]){
                for (int j = i * 2; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
        
        for(int i = 2; i <= n; i++){
            if(prime[i] == true) answer++;
        }
        
        return answer;
       
    }
}

 

정확성 테스트

테스트 1 〉	통과 (0.02ms, 75.5MB)
테스트 2 〉	통과 (0.03ms, 80MB)
테스트 3 〉	통과 (0.05ms, 78.4MB)
테스트 4 〉	통과 (0.08ms, 71.1MB)
테스트 5 〉	통과 (0.11ms, 87.3MB)
테스트 6 〉	통과 (0.63ms, 80.8MB)
테스트 7 〉	통과 (0.31ms, 77.5MB)
테스트 8 〉	통과 (0.43ms, 74.8MB)
테스트 9 〉	통과 (0.65ms, 87.9MB)
테스트 10 〉	통과 (14.08ms, 99.1MB)
테스트 11 〉	통과 (17.20ms, 75.9MB)
테스트 12 〉	통과 (11.18ms, 90MB)

효율성 테스트

테스트 1 〉	통과 (30.60ms, 54.8MB)
테스트 2 〉	통과 (30.01ms, 54.5MB)
테스트 3 〉	통과 (28.33ms, 54.9MB)
테스트 4 〉	통과 (26.74ms, 55.2MB)

 

 

오 이렇게 보니까 확실히 다름.

아 근데 생각해보니까 위의 곱셈 방식에서는 tmp 변수를 할당해서 사용해서 그런 것 같기도 함. 그래서 그걸 없애고 다시 시도해봄

import java.util.*;

class Solution {
    public int solution(int n) {
        
        // 2~n 까지의 수를 자료구조에 담기.
        // 2~n/2까지 돌면서 해당 숫자의 배수를 n에서 제거
        // 예를 들어, 처음에 n에 2가 들어있으니까(==true), 자료구조에서 2의 배수 싹 지움(false)
        // 그 뒤에 3의 배수 싹 지움(본인 제외)
        // ,,, 뒤에 자료구조에 남아있는 가장 작은 수를 기준으로 배수 지우기
        // 남은 거 세기
        
        int answer = 0;
        // 사용할 자료구조: boolean 타입의 배열
        boolean[] prime = new boolean[n+1];
        
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        
        for(int i = 2; i <= n/2; i++){
            if(prime[i]){
                for (int j = 2; i * j <= n; j++) {
                    prime[i * j] = false;
                }
            }
        }
        
        for(int i = 2; i <= n; i++){
            if(prime[i] == true) answer++;
        }
        
        return answer;
        
        
        // // for 2 ~ n
        // // i가 소수인지 아닌지 판단
        // if(n >= 2){
        //     answer += 1;
        // }
        // for(int i = 3; i <= n; i+=2){
        //     if (i==3 || i==5 || i==7){
        //         answer +=1;
        //         continue;
        //     }
        //     if (i%3 == 0) continue;
        //     if (i%5 == 0) continue;
        //     if (i%7 == 0) continue;
        //     for(int j = 2; j <= i/2; j++){
        //         if(i%j == 0){
        //             break;
        //         }
        //         if(j == i/2){
        //             answer += 1;
        //         }
        //     }
        // }
        // return answer;
    }
}

 

이렇게 했는데

정확성 테스트

테스트 1 〉	통과 (0.02ms, 70.8MB)
테스트 2 〉	통과 (0.03ms, 86.1MB)
테스트 3 〉	통과 (0.07ms, 82.8MB)
테스트 4 〉	통과 (0.08ms, 73.2MB)
테스트 5 〉	통과 (0.06ms, 85MB)
테스트 6 〉	통과 (0.66ms, 77.6MB)
테스트 7 〉	통과 (0.18ms, 77.7MB)
테스트 8 〉	통과 (0.41ms, 77.5MB)
테스트 9 〉	통과 (0.70ms, 88.3MB)
테스트 10 〉	통과 (10.96ms, 93.1MB)
테스트 11 〉	통과 (19.40ms, 79.9MB)
테스트 12 〉	통과 (11.01ms, 90.3MB)

효율성 테스트

테스트 1 〉	통과 (28.96ms, 54.9MB)
테스트 2 〉	통과 (27.53ms, 55.2MB)
테스트 3 〉	통과 (28.86ms, 54.6MB)
테스트 4 〉	통과 (25.92ms, 54.7MB)

 

오 비슷함. 아무래도 중간에 tmp 변수를 할당해야해서 그런 것 같음

 

이 알고리즘에서 진짜 시간이 걸리는 부분은 i * j 계산이 아니라, prime[인덱스] = false라고 배열의 메모리 칸에 값을 쓰는 작업입니다.

• CPU 연산 속도는 빛의 속도인데, 메모리(RAM)에 접근하는 속도는 상대적으로 거북이거든요.
• 곱셈을 하든 덧셈을 하든 어차피 **"배열의 특정 칸을 찾아가서 값을 바꾼다"**는 행위는 똑같기 때문에 여기서 시간이 다 소요되는 겁니다.

이렇다 함!