Array_소수_Sieve of Eratosthenes

✅ 아리스토테네스 체

class Main {
    public int solution(int n){
    int answer = 0;
    int[] intArr= new int[n+1]; //처음 빈 배열 생성되면 모든 값은 0
    for(int i=2; i<n; i++){
        if(intArr[i] == 0){
            answer++;
            for(int j=i; j<n; j=j+i){
                intArr[j] = 1;
            }
        }
    }
    return answer;

}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}


//⭐️input:
//20
//⭐️output:
//8

🔵 ThingsILearned

✔️ Array의 index를 마음대로 바꿀 수 있구나

Array의 index는 항상 0에서부터 시작할 필요가 없다. 내가 마음대로 정할 수 있다.

🟢 j for문 다르게 돌기

class Main {
    public int solution(int n){
    int answer = 0;
    int[] intArr= new int[n+1]; //처음 빈 배열 생성되면 모든 값은 0
    for(int i=2; i<n; i++){
        if(intArr[i] == 0){
            answer++;
           for(int j=1; i*j<n+1; j++){
               intArr[i*j] = 1;
           }
        }
    }
    return answer;

}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}

🟢 2중 for문으로 풀기(시간초과)

class Main {
    public int solution(int n){
    int answer = 1;

    for(int i=3; i<n+1; i++){
        ArrayList<Integer> canBeDividedBy= new ArrayList<>();
        for(int j=2; j<i; j++){
            if(i%j==0) canBeDividedBy.add(j);
        }
        if(canBeDividedBy.isEmpty()) answer++;
    }
    return answer;

}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}