BOJ 1978. 소수 찾기

BOJ 1978. 소수 찾기

풀이

소수란 1과 자기 자신밖에 존재하지 않는 수

소수 구하기 1

boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }

    for (int i = 2; i <= n-1; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 N이 소수가 되려면 2보다 크거나 같고, N-1보다 작거나 같은 수로 나누어 떨어지면 안 된다. O(N)의 시간 복잡도를 가진다

소수 구하기 2

boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }

    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

N이 소수가 되려면 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
N = a \* b (a≤b) 일 때 

• a가 작을수록 b는 크다
• 가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 b N/2를 넘지 않는다
  • a가 2라 하였을 때  N = 2 * (N/2)이므로

O(N/2)==O(N)의 시간 복잡도를 가진다

소수 구하기 3

boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

N이 소수가 되려면 2보다 크거나 같고, 루트 N보다 작거나 같은 수로 나누어 떨어지면 안 된다.

• N이 소수가 아니라면 N = a \* b (a≤b)로 나타낼 수 있다
• a와 b의 차이가 가장 작은 경우는 루트 N이다

O(√N)의 시간 복잡도를 가진다.

Java

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int count = 0;
        while (t-- > 0) {
            int n = sc.nextInt();
            if (isPrime(n)) count++;
        }
        System.out.println(count);
        sc.close();
    }

    static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Kotlin

fun main() {
    readLine()
    println(readLine()!!.split(' ').map(String::toInt).filter(::isPrime).size)
}

private fun isPrime(n: Int) = n != 1 && !(2 until n).any { n % it == 0 }

소스풀이

github.com/beomjo/algorithm-study/blob/main/BOJ/java/1978.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/1978.kt