처음 풀이(시간 초과)
public static void isPrime(int n) {
int k = 0;
for(int i=2;i<=n;i++) {
int count = 0;
for(int j=1;j<=i;j++) {
if(i%j==0) {
count++;
}
}
if(count==2) k++;
}
System.out.println(k);
}1. 그냥 i의 값을 j로 나눠서 0이 나오는 경우일때 count를 증가 시켰고
2. count가 2이면 소수이기 때문에 k를 증가시켰다.
3. 다만 반복문이 끝까지 다 돌아가기 때문에(두번째 반복문에서 기준점을 2로 시작하고 j<i/2했을 때 조건식을 만족하지 않으면 소수의 값을 증가시키는 방향으로 처리하는 방법이 있었다)
에라토스테네스의 체
- 이걸 이해하기까지 좀 걸렸었던거 같다.
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;
}
}
}
return answer;
}간단하다.
1. 만약에 20이라는 값이 입력되면
2. 배열을 만든다. 크기 20+1 / 1을 더해주는 이유는 배열의 인덱스를 소수처럼 활용하기 위해서이다.
3. 첫번째 반복문을 돈다. 기준점은 2부터 만약 배열[i]의 값이 0이라면 소수이므로 answer(만들어 주어야)를 증가 시킨다.
4. 두번째 반복문을 돌때 기준점 j는 i j<=n까지 돌아야 한다. j = j+i 이부분이 핵심이다.
j = i+j
i가 2이다. 2의 배수들은 다 소수가 아니다. 배열[j] = 1을 넣어주자.
i가 3이다. 3의 배수들은 다 소수가 아니다. 배열[j] = 1을 넣어주자.
i가 4이다. 배열[i] = 1이다. 조건 만족하지 않으니 5로 넘어간다.
i가 5이다. 5의 배수들은 다 소수가 아니다. 배열[j] = 1을 넣어주자.
그러면 헷갈릴 수도 있다. 배열[2] = 1을 넣어주면 어떻게 하냐. 소수이지 않느냐?
위의 처음 반복문을 실행하면서 이미 더해주기 때문에 상관이 없다. answer++
5. 소수의 값이 저장된 answer를 리턴한다.
아마 프로그래머스에도 비슷한 문제가 있는데 에라토스테네스의 체를 이용해서 풀면 효율성 테스트?
통과할 수 있었다.
