(Array)에라토스테네스체 / 뒤집은 소수

에라토스테네스체

✏️ 문제

* 설명
자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

* 입력
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

* 출력
첫 줄에 소수의 개수를 출력합니다.

🔍풀이

public int solution(int n){
	int answer = 0;
    int[] ch = new int[n+1];
    for(int i = 2; i <= n; i++){
    	if(ch[i]==0){
        	answer++;
            for(int j=i; j <=n; j=j+i) ch[j] = 1;
        }
    }
}

뒤집은 소수

✏️ 문제

* 설명
N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면
그 소수를 출력하는 프로그램을 작성하세요.
예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 
단 910를 뒤집으면 19로 숫자화 해야 한다.
첫 자리부터의 연속된 0은 무시한다.

* 입력
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다.
각 자연수의 크기는 100,000를 넘지 않는다.


* 출력
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.

🔍풀이

public class Main {

    public boolean isPrime(int reversed){
        if(reversed == 1) return false;
        for(int i = 2; i < reversed; i++){
            if(reversed % i ==0) return false;
        }
        return true;
    }

    public ArrayList<Integer> solution(int n, int[] arr) {
        ArrayList<Integer> answer = new ArrayList();
        for (int i = 0; i < n; i++) {
            int reversed = 0;
            int tmp = arr[i];
            while(tmp > 0){

                reversed = reversed * 10 + tmp % 10; // 1
                tmp = tmp/10;
            }
            if(isPrime(reversed)) answer.add(reversed);
        }

        return answer;
    }

💡팁

여기서 굳이 에라토스테네스체 소수 방법을 사용하지 않은 이유는,
첫 번째 문제에서는 20만개의 수가 주어지면 20만개의 수가 0~해당 번호까지 계속 반복을 돌며 
약수가 없는지 확인을 해야하기 때문에 숫자가 커질수록 반복 회수가 매우 커진다.
따라서 처음 약수를 확인할 때, 배수의 자리에다가 다 1을 채워넣는 것이 빠르다.
ex)2의 배수만 넣어도 10만개의 숫자가 for문을 돌지 않게 된다.

반면 위의 문제는 100개 이하의 수가 주어지기 때문에 해당 수의 약수로
비교해도 큰 문제가 없는 것.