1. Problem 📃

[ 소수 찾기 ]

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

2. Constraint 🔗

3. Solution 🔑

1. 주어진 수(n)에 +1을 한 만큼의 배열을 생성 (인덱스를 보기 편하기 위해)
2. 배수가 나오지 않았던 수는 0으로 판단하고, 0이면 정답의 갯수를 증가.
3. 처음 수들의 배수를 구하여 n까지 나온 수들은 배열에서 1로 판단 (소수x)
4. 정답 값을 return

< 에라토스테네스의 체 >
1. 주어진 수(n)에 +1을 한 만큼의 배열을 생성 (인덱스를 보기 편하기 위해)
2. 본인들을 제외 한 { 2, 3, 5, 7 } 의 배수들의 인덱스 값은 1로 처리.
3. 배열을 2부터 n까지 for문으로 값을 확인하여 0일 때만 정답 갯수 증가
4. 정답 값을 return

4. Code 💻

class Solution {
	public int solution(int n) {
		int[] arr = new int[n+1];
		int answer = 0;
		
		for(int i=2; i<=n; i++) {
			int circle = 1;
			if(arr[i] == 0) {
				answer++;
				while(i*circle <= n) {
					arr[i*circle] = 1;
					circle++;
				}
			}
		}		
		return answer;
	}
}

얘 왜 안 되는지 확인해보기.

- re. 121이 제거가 안 됨. (1 ,11, 121) ( 2021. 12. 27 (월) )

import java.util.Arrays;
class Solution {
	public int solution(int n) {
		int[] arr = new int[n+1];
        int[] prime = {2, 3, 5, 7};
        int answer = 0;
        
        for(int i=0; i<4; i++){
            int j=2;
            while(prime[i]*j<=n){
                arr[prime[i]*j] = 1;
                j++;
            }
        }
        System.out.println(Arrays.toString(arr));
        
        for(int i=2; i<=n; i++){
            if(arr[i] != 1){
                answer++;
            }
        }
		return answer;
	}
}

5. Growth 🍄

< 에라토스테네스의 체 >
간단한 소수 구하는 알고리즘으로,
“소수가 되는 수의 배수들을 제외하면 남은 수는 소수가 된다”라는 알고리즘.