[Programmers] #120846 - 합성수 찾기 [Java][C++][Python]

문제 링크

---

1. 아이디어

합성수는 약수가 세 개 이상인 수, 곧 1도 소수도 아닌 수다.

가장 단순한 방법은 각 수를 직접 나눠 보는 것이다. 1부터 n까지의 각 i에 대해 2 이상 i 미만의 수로 나눠떨어지는 것이 하나라도 있으면 i는 합성수다. 1과 소수에는 그런 약수가 없으므로 자연히 세어지지 않는다.

두 번째 방법은 에라토스테네스의 체를 활용하는 것으로 n 이하의 소수를 한 번에 걸러낸 뒤, 2부터 n까지 중 소수로 표시되지 않은 수의 개수를 세는 방법이 있다.

---

2. 복잡도

접근	시간	공간
완전탐색	$O(N^2)$	$O(1)$
에라토스테네스의 체	$O(N \log \log N)$	$O(N)$

($N$ = 입력값 n)

---

3. 코드

풀이: 완전탐색 [Java][C++][Python]

class Solution {
    public int solution(int n) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    cnt++;
                    break;
                }
            }
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                cnt++;
                break;
            }
        }
    }

    return cnt;
}

def solution(n):
    return sum(1 for i in range(1, n + 1) if any(i % j == 0 for j in range(2, i)))

any(i % j == 0 for j in range(2, i))는 2 이상 i 미만에 약수가 하나라도 있으면 True를 반환하고, 첫 약수를 찾는 즉시 순회를 멈춘다.

---

풀이 2: 에라토스테네스의 체 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(int n) {
        boolean[] isPrime = sieve(n);
        int cnt = 0;

        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]) cnt++;
        }

        return cnt;
    }

    static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[1 + n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        return isPrime;
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<bool> sieve(int n) {
    vector<bool> is_prime(1 + n, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return is_prime;
}

int solution(int n) {
    vector<bool> is_prime = sieve(n);
    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        if (!is_prime[i]) cnt++;
    }

    return cnt;
}

def sieve(n):
    is_prime = [True] * (1 + n)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            is_prime[i * i :: i] = [False] * len(range(i * i, n + 1, i))

    return is_prime


def solution(n):
    is_prime = sieve(n)
    return sum(1 for i in range(2, n + 1) if not is_prime[i])

---