6. 뒤집은 소수

문제

---

 

 

코드
1. 나눗셈 

public static void solution(int[] a) {
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            String reversed = new StringBuilder(String.valueOf(a[i])).reverse().toString();
            b[i] = Integer.parseInt(reversed);
        }

        for (int i = 0; i < b.length; i++) {
            if (b[i] < 2 || !isPrime(b[i])) {
                b[i] = 0; //소수가 아니면 0으로 만듬
            }
        }

        for (int r : b) {
            if (r != 0) System.out.print(r + " ");
        }
    }

    public static boolean isPrime(int a) {
        if (a < 2) return false;
        for (int i = 2; i <= Math.sqrt(a); i++) {
            if (a % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        sc.nextLine();
        int[] b = new int[a];
        for (int i = 0; i < a; i++) {
            b[i] = sc.nextInt();
        }
        solution(b);
    }

 

 

에라토스테네스의 체를 사용하지 않고, 개별적으로 소수를 판별하기 위해 나눗셈을 사용했다. 

 

코드
2. 에라토스테네스의 체

 

public static void solution(int[] a) {
    // 반전된 숫자의 최대값을 찾기 -> 배열의 크기를 결정 짓기 위해서
    int max = 0;
    for (int num : a) {
        String reversed = new StringBuilder(String.valueOf(num)).reverse().toString();
        int reversedNum = Integer.parseInt(reversed);
        if (reversedNum > max) {
            max = reversedNum;
        }
    }

    // 에라토스테네스의 체를 위한 배열 초기화
    boolean[] isPrime = new boolean[max + 1];
    for (int i = 2; i <= max; i++) {
        isPrime[i] = true; // 모든 수를 소수로 가정
    }
    isPrime[0] = false; // 0은 소수가 아님
    isPrime[1] = false; // 1도 소수가 아님

    // 에라토스테네스의 체 알고리즘 적용
    for (int i = 2; i * i <= max; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= max; j += i) {
                isPrime[j] = false; // 배수 지우기
            }
        }
    }

    // 각 숫자를 반전하여 소수 여부 판단
    for (int num : a) {
        String reversed = new StringBuilder(String.valueOf(num)).reverse().toString();
        int reversedNum = Integer.parseInt(reversed);
        if (isPrime[reversedNum]) {
            System.out.print(reversedNum + " "); // 소수인 경우 출력
        }
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    sc.nextLine();
    int[] b = new int[a];
    for (int i = 0; i < a; i++) {
        b[i] = sc.nextInt();
    }
    solution(b);
}

 

 

장단점 

 

1. 직접 나눗셈을 이용한 소수 판별
장점 
단순성: 구현이 간단하고 기본적인 수학 원리를 사용해서 이해하기 쉬운 코드이다.
메모리 사용: 추가적인 배열을 사용하지 않기 때문에 메모리 소모가 적음.
단점
비효율성: 큰 숫자에 대해서는 성능이 좋지 않을 수 있다. 모든 숫자에 대해 개별적으로 소수를 판별하므로, 많은 수를 처리할 때 느려질 수 있습니다. 시간 복잡도 -> 각 숫자에 대해 O(√n)의 시간이 필요하므로, 많은 숫자를 검사할 경우 비효율적.

2. 에라토스테네스의 체
장점
효율성: 범위 내의 모든 소수를 한 번에 찾아야 할 때 매우 빠르다. 시간 복잡도는 O(n log log n)으로, 큰 범위의 소수를 찾는 데 효과적.
리스트 활용: 소수를 한 번에 찾기 때문에, 후속 작업에서 소수를 재사용할 수 있음.
단점
복잡성: 구현이 조금 더 복잡하며, 초기 설정이 필요함.
메모리 사용: 소수 여부를 저장하기 위한 배열이 필요하므로 메모리 사용량이 많아짐. 특히, 큰 숫자의 경우 많은 메모리를 소모.

 

 

결론

일반적인 작은 수의 소수 판별이 필요할 경우 :
간단한 나눗셈 방법을 사용하는 것이 좋다. 구현이 쉽고 직관적이기 때문이다.

큰 범위의 소수를 빠르게 찾고 싶다면 :
에라토스테네스의 체를 사용하는 것이 더 나은 선택이다.

특히 많은 숫자를 효율적으로 처리해야 하거나, 소수 목록이 필요한 경우에 유리하다.