백준 / 2581 소수

문제

풀이

다음 문제는 에라스토테네스의 체로 M이상 N이하의 자연수 중 소수인 것을 골라 소수의 합과 최솟값을 찾는 문제인데 이 문제를 풀기 위해서 다양한 방법이 있지만 이번에는 알고리즘을 통해 풀어보자.
우선 '에라토스테네스의 체'가 무엇인지 예를들어 알아보자, 2부터 N까지의 소수를 구한다고 하면,

1. 2부터 N까지의 모든 수를 나열한다.
2. 아직 지워지지 않은 수(배수가 되는 수) 중에서 가장 작은 수를 찾는다.
3. 그 수는 소수이다.
4. 이제 그 수의 배수를 모두 지운다. 를 반복한다.
   

• 첫 번째 소수인 2의 배수를 지우고
• 두 번째 순서의 소수 3의 배수를 지운다.
• 다음과 같이 소수의 배수를 지우면 현재 정해놓은 N인 100까지의 소수를 구할 수 있다.

import java.util.Scanner;

public class Num2581 {
	
	public static boolean prime[]; // 소수를 체크할 배열

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int M = in.nextInt();
		int N = in.nextInt();
		
		
		prime = new boolean[N+1]; // 0~N 생성
		get_prime();
		
		// 소수가 아닌 index = true
		// 소수인 index = false
		// 소수의 합, 최소값
		int sum = 0;
		int min = Integer.MAX_VALUE;
		for(int i = M; i<=N; i++) {
			if(prime[i] == false) {
				sum += i;
				if(min == Integer.MAX_VALUE) {
					min = i;
				}
			}
		}
		
		if(sum == 0) {
			System.out.println(-1);
		} else {
			System.out.println(sum);
			System.out.println(min);
		}
		
	}
	// 에라토스테네스 체 알고리즘
	private static void get_prime() {
		prime[0] = true;
		prime[1] = true;
		// 제곱근 함수 : Math.sqrt()
		for(int i = 2; i <= Math.sqrt(prime.length); i++) {
			// i의 배수들을 걸러주기 위한 반복문
			for(int j = i*i; j < prime.length; j+= i) {
				prime[j] = true;
			}
		}
	}
}

코드

코드를 입력하세요

시간 복잡도

이중 for문이라 시간 복잡도가 O(n^2)인것 같지만 그렇지 않다.
에라스토테네스의 체 시간복잡도는 O(Nlog(logN))인데 과정이 너무 복잡하여 훗날에 다시 과정을 추가해 보겠다 ㅜ

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