[프로그래머스]연습문제 : 소수 찾기 (level 1)

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기 | 프로그래머스

 

class Solution {
  public int solution(int n) {
 
    // 에라토스테네스의 체. 소수여부를 미리 판정해놓기
    boolean[] arrNotPrime = new boolean[1000001];
    for (int i = 2; i < arrNotPrime.length; i++) {
 
      // 어느 수의 배수이면 arrNotPrime배열에 true체크 == 소수가 아니라는 뜻
      if (arrNotPrime[i] == false) {
        for (int j = 2; j * i < arrNotPrime.length; j++) {
          arrNotPrime[j * i] = true;
        }
      }
    }
    
    // 소수이면 카운트
    int answer = 0;
    for (int i = 2; i <= n; i++) {
      if (arrNotPrime[i] == false) {
        answer++;
      }
    }
 
    return answer;
  }
}

 

 

 

소수문제 오랜만!