[백준-Java] 기본수학2 - 1, 2, 3번

이번 문제들은 수업에서 자주 썼던 알고리즘들이다.
하지만 기억이 안나서 좀 걸렸다...더 열심히 공부를 안한 나를 원망했다.

1978번) 소수찾기, 2581번) 소수

두 문제 모두 소수를 이용한 문제이다.
여기서 소수는 1과 자기 자신만을 나눌 수 있는 자연수이다. '2,3,5,7,11,13...'이 이에 해당된다.

첫번째 방법으로 2부터 n-1까지 나눌 수 있는 수를 제외하는 방법이 있다.
n-1을 하는 이유는 자기자신이 포함되어서는 안되기 때문이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] arr = new int[T];
        int count = 0;
        String N = br.readLine();
        for(int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(N.split(" ")[i]);
            count += sosu(arr[i]);
        }
        System.out.println(count);
    }
    public static int sosu(int n){ // 소수를 판별하는 코드
        if(n < 2 && n > 0) return 0;
        else if(n == 2) return 1;
        for(int i = 2; i < n; i++){
             if(n % i == 0) return 0;
        }
        return 1;
    }
}

두번째 방법으로는 '에라토스테네스의 체'를 이용한 방법이다.

간단하게 설명해서 1~100까지의 수 중에서 소수를 찾는다 하면,
2를 제외한 2의 배수들을 모두 지우고,
3을 제외한 3의 배수들을 모두 지우고,
5를 제외한 5의 배수들을 모두 지우고...
를 반복하여 100까지의 소수를 찾는 방법이다.

위의 방법을 채용하면 훨씬 빠른 실행시간을 가질 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[] arr = new int[M+1];
        int min = 0;
        int sum = 0;

        for(int i = 2; i < M+1; i++){
            arr[i] = i;
        }
        for(int i = 2; i < M+1; i++){
            if(arr[i]==0) continue;
            else{
                for(int j = i+i; j < M+1; j += i){
                    if(arr[j]== 0) continue;
                    else arr[j] = 0;
                }
            }
        }
        for(int i = 0; i < M+1; i++){
            if(arr[i] != 0) {
                if(arr[i] >= N){
                    if(min == 0) min = arr[i];
                    sum += arr[i];
                }
            }
        }
        if(sum == 0) System.out.println(-1);
        else{
            System.out.println(sum);
            System.out.println(min);
        }
    }
}

11653번) 소인수분해

소인수분해도 비슷한 방법이긴 하나, 실행시간 단축을 위해 주어진 N의 제곱근 값까지만 반복하는 것으로 한다.

예를 들어 100이라 하면 (2,50), (4,25)...(10,10)까지 나눠진다.
10보다 큰 값을 나누면 미리 나눈 값과 같은 결과가 나온다. (2,50)과 (50,2)은 같은 결과라는 뜻이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int n = (int)Math.sqrt(N);
        for(int i = 2; i <= n; i++){
            while(N % i == 0) {
                N = N / i;
                System.out.println(i);
            }
        }
        if(N != 1) System.out.println(N);
    }
}