소수 찾기

문제 : 소수 찾기

풀이

for (int i = 2; i <= n; i++) {
   boolean flag = true;

• 1은 소수가 아니기 때문에 2부터 n까지 반복

• boolean 타입의 flag라는 변수를 생성하여 소수가 아니면 true를 출력하도록 설정

for (int j = 2; j <= Math.sqrt(i); j++) {
   if(i % j == 0) {
      flag = false;
      break;
   }
}

• j는 2부터 i를 제곱근한 수만큼 반복

• 만약 배열에 있는 숫자가 j로 나누어떨어지면 소수가 아니기 때문에 flag를 false로 변환

if (flag == true) answer++;

• flag가 그대로 true라면 소수라는 뜻이므로 숫자를 카운트하여 개수를 찾음

전체 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 2; i <= n; i++) {
            boolean flag = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if(i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag == true) answer++;
        }
        return answer;
    }
}

에라토스테네스의 체 사용 1.

public static int solution2(int n) {
    int answer = 0;
    boolean[] prime = new boolean[n+1];
    prime[0] = prime[1] = true;
    for (int i = 2; i <=Math.sqrt(prime.length); i++) {
        if (prime[i]) continue;
        for (int j = i * i; j < prime.length; j += i)
            prime[j] = true;
    }
    for(boolean check : prime){
        if(!check){
            answer++;
        }
    }
    return answer;
}

boolean[] prime = new boolean[n+1];

• n+1만큼의 크기를 가진 배열 선언

prime[0] = prime[1] = true;

• 0과 1은 소수가 아니므로 true

for (int i = 2; i <=Math.sqrt(prime.length); i++) {
    if (prime[i]) continue;
    for (int j = i * i; j < prime.length; j += i)
      prime[j] = true;
}

• 0과 1은 소수가 아니기 때문에 2부터 prime 길이의 제곱까지 반복

• 이미 한 번 체크 된 배열이면 continue

• i의 배수라면 소수가 아니므로 true
  

for(boolean check : prime){
   if(!check){
      answer++;
   }
}

• 남은 prime 배열에 남은 숫자들을 for문을 사용해 true가 아닐경우(소수일 경우) answer를 더해줌

에라토스테네스의 체 사용 2.

 public static boolean[] prime = new boolean[1000001];
    // 소수 판별
    public  void setPrime(){
        prime[0] = prime[1] = true;
        for(int i = 2; i <= Math.sqrt(prime.length); i++){
            if(prime[i] == true) continue;
            for(int j = i * i; j < prime.length; j += i)
                prime[j] = true;
        }
    }
    public  int solution(int n) {
        int answer = 0;
        setPrime();
        for(int i = 1; i <= n; i++){
            if(prime[i] == false)
                answer++;
        }
        return answer;
    }
}

for(int i = 1; i <= n; i++){
   if(prime[i] == false)
     answer++;
}

• 소수일 경우(=false) 카운트 해줌(=answer)