[Algorithm] - 소수 (에라토스테네스의 체)

소수 알고리즘 - 에라토스테네스 체

• 2부터 n까지 모든 수를 나열 -> 자기 자신을 제외한 배수를 모두 지운다.
• 위의 과정을 반복하면 소수가 남는다.
• 이중 for문을 사용해야 하지만, 값이 2일 때 N /2 , 3일 때 N / 3 점점 커지므로 O(logN)이 된다.
  • 1 + 1/2 + 1/3 + ... 의 합이 O(logN)이라는 원리와 동일
• 2부터 자기자신까지 모두 비교하면 O(n^2) , 에라토스테네스의 체를 실행하면 O(logN)의 시간복잡도를 갖는다.
• 단, 1천만~1억 까지 소수는 없다 (문제에 따라 판단 필요)

 public static boolean isPrime(int num) {
        if(num == 1) return false;
        else {
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) return false;
            }
        }
        return true;
    }

• 2부터 자기자신을 모두 비교하는 방법

BOJ(2581) - 소수 (JAVA)

https://www.acmicpc.net/problem/2581

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> arr = new ArrayList<>();
    static int m,n;
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        boolean[] prime = findPrime(n);
        chkNum(prime);
        if (arr.size() == 0) System.out.println(-1);
        else {
            System.out.println(sum());
            System.out.println(Collections.min(arr));
        }
    }

    public static boolean[] findPrime(int num) {
        boolean[] arr = new boolean[num+1];
        arr[0] = arr[1] = true;
        for (int i = 2; i <= num; i++) {
            if (!arr[i]) {
                for (int j=i*2; j<=n; j+=i){
                    if (!arr[j]) arr[j] = true;
                }
            }
        }
        return arr;
    }

    public static void chkNum(boolean[] prime) {
        for (int i = m; i <= n; i++) {
            if (!prime[i]) arr.add(i);
        }
    }

    public static int sum() {
        int result = 0;
        for (int x : arr) result += x;
        return result;
    }
}

• boolean 또는 int 형 배열을 n+1크기로 만든 다음, 2부터 배수를 지워나간다. 지우고 남은 수가 소수가 된다.

BOJ(1978) - 소수 찾기 (JAVA)

https://www.acmicpc.net/problem/1978

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static int[] prime;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(sc.nextInt());
        }
        int max = Collections.max(arr);
        prime = new int[max+1];
        prime[0] = prime[1] = 1;
        isPrime(max);
        int result = 0;
        for (int i=0; i<arr.size(); i++) {
            if (prime[arr.get(i)] == 0) result += 1;
        }
        System.out.println(result);
    }

    public static void isPrime(int max) {
        for (int i=2; i<=max; i++) {
            if (prime[i] == 0) {
                for (int j=i*2; j<=max; j+=i) {
                    prime[j] = 1;
                }
            }
        }
    }
}