[백준] 약수, 배수와 소수

11653

소인수분해

소인수 분해 : 정수를 소수들의 곱으로 표현하는 방법 (주어진 정수를 구성하는 소수들의 목록을 구하는 것)

소수(Prime Number): 1과 자기 자신만으로 나누어 떨어지는 수 (예: 2, 3, 5, 7, …).

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        // 소인수분해 시작
        for (int i = 2; i <= Math.sqrt(N); i++) {
            while (N % i == 0) {
                System.out.println(i); // 소인수 출력
                N /= i; // N을 i로 나눈 몫으로 갱신
            }
        }

        // 남은 숫자가 소수인 경우 출력
        if (N > 1) {
            System.out.println(N);
        }
    }
}

2581

소수

double Math.sqrt(double value); //

: 입력 값의 제곱근을 double로 반환

 

        System.out.println(Math.sqrt(4));    // 2.0

        System.out.println(Math.sqrt(16));   // 4.0

        System.out.println(Math.sqrt(10));   // 3.1622776601683795

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();

        int sum = 0; // 소수의 합
        int min = Integer.MAX_VALUE; // 소수의 최솟값
        boolean foundPrime = false; // 소수 발견 여부

        // M에서 N까지 모든 수에 대해 소수 판별
        for (int i = M; i <= N; i++) {
            if (isPrime(i)) {
                sum += i; // 합에 더하기
                if (i < min) {
                    min = i; // 최솟값 갱신
                }
                foundPrime = true;
            }
        }

        // 결과 출력
        if (foundPrime) {
            System.out.println(sum);
            System.out.println(min);
        } else {
            System.out.println(-1);
        }
    }

    // 소수 판별 함수
    private static boolean isPrime(int num) {
        if (num < 2) {
            return false; // 1과 0은 소수가 아님
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false; // 약수가 존재하면 소수가 아님
            }
        }
        return true; // 소수
    }

}

2501

약수 구하기

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();

        ArrayList<Integer> divisors = new ArrayList<>();

        // N의 약수 찾기
        for (int i = 1; i <= N; i++) {
            if (N % i == 0) {
                divisors.add(i);
            }
        }

        // K번째 약수 출력 또는 0 출력
        if (divisors.size() >= K) {
            System.out.println(divisors.get(K - 1)); // K번째 약수
        } else {
            System.out.println(0); // 약수의 개수가 K보다 적음
        }


    }
}