[알고리즘] 소수 (Prime)

소수 구하기

- 숫자 N의 소수 판정 방법

1 ~ $\sqrt{N}$까지 N을 나누어 떨어지게 하는 수가 있는지를 확인 

 

- 에라토스테네스의 체 사용하기

각 수는 임의의 값 n * n 제곱하여 나오는 n보다 큰 값을  ( i * i < N )

0과 1은 소수가 아님

boolean 배열을 만들고, 소수가 아닌 값을 탐색하면서 true로 만들기

 

소수가 아닌 값 처리 시 i*i가 시작인 이유!

-> 5의 경우 5*2 / 5*3 / 5*4 / 5*5 / ... 로 진행되며,

-> 이때 2, 3, 4(2,2)는 앞선 값으로 인해서 소수가 아니라고 처리되기 때문에 

 

10,000까지의 소수의 개수 : 1,229개

 

 

소수 구하는 코드 (Java)

private static boolean isPrime(int num) {
    if (num < 2) {
        // 소수가 아님
        return false;
    }

    if (num == 2) {
        // 소수
        return true;
    }
    
    for (int i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            // 소수가 아님
            return false;
        }
    }
    // 소수
    return true;
}

 

 

 

에라토스테네스 구현 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(st.nextToken()); // 소수를 구할 범위
		
		// 소수는 false
		boolean[] prime = new boolean[N + 1];
		prime[0] = true;
		prime[1] = true;


		for (int i = 2; i * i <= N; i++) {
			// 현재 탐색하는 수(i)가 소수(false)라면
			if(!prime[i]) {
				// 배수를 소수가 아니(true)라고 처리
				// 시작은 자기의 제곱으로 시작
				for (int j = i*i; j <= N; j+=i) {
					prime[j] = true;
				}
			}
		}
		
		for (int i = 0; i < prime.length; i++) {
			if (!prime[i]) {
				System.out.print(i +" ");
			}
		}
	}
}

 

 

 

소수 추천 문제

- 소수 기본 문제

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

 

- 소수 구하기

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

 

- 골드바흐의 추측

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

※ Hint : 가운데에서부터 양쪽으로 1씩 증감하면서 찾아나가면 된다!

 

- 신기한 소수

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