백준 - 단계별로 풀어보기 - JAVA (8단계 : 기본 수학 2 / 6문제) (2022.12.27 화)

1단계 : 1978번 / 소수 찾기

import java.util.Scanner;

public class Main{
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int count = 0;
        for(int i=0; i<N; i++){
            int a = sc.nextInt();
            if (a == 1) { count--;}
            boolean flag = true;
            for(int j=2; j<=(a/2); j++){
                if (a%j == 0){
                    flag = false;
                    break;
                }
            }
            if(flag) {count++;}
        }
        System.out.println(count);
    }
}

* a의 약수는 1~a/2 범위에 존재함.

---

2단계 : 2581번 / 소수

 

import java.util.Scanner;

public class Main{
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();

        int sumPrime = 0; // 소수합
        int minPrime = 0; // 최소 소수

        for(int i=M; i<=N; i++){
            boolean flag = true;
            for (int j=2; j<=(i/2); j++){
                if (i%j == 0){flag = false; break;}
            }
            if (i == 1) {sumPrime --; minPrime = 0;}
            if (flag && (sumPrime == 0)){minPrime = i;}
            if (flag) {sumPrime += i;}
        }

        if (minPrime == 0){
            System.out.println(-1);
        } else{
            System.out.println(sumPrime+"\n"+minPrime);
        }
    }
}

* M = 1일 경우 sumPrime -- ; 연산을 통해 예외처리 (1을 소수로 보는것을 방지)

* 최소 소수를 찾기 위해 '소수임이 판명된 경우(flag == true)' 와 '소수의 합이 0인 경우'를 모두 만족한 경우 해당 수를 최소 소수로 한다.

* 최소 소수가 0인 경우 (소수가 없는 경우) '-1'을 출력한다.

---

3단계 : 11653번 / 소인수분해

import java.util.Scanner;

public class Main{
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); 

        int index = 0;
        int[] num = new int[N];

        int i = 2;
        while(i <= N){
            while (N%i == 0){
                N = N / i;
                num[index] = i;
                index++;
            }
            i++;
        }

        i = 0;
        while(num[i] != 0){
            System.out.println(num[i]); i++;
        }
        
    }
}

1) 2~N까지의 소수를 구한다.

2) 소수가 등장하면 그때마다 N에 나눠본다.

3) 나눠지지 않을때까지 해당 소수를 반복적으로 나눈다.

4) 나눠지지 않는다면 다음 소수를 찾는다.

---

4단계 : 1929번 / 소수 구하기

import java.util.Scanner;

public class Main{

    public static boolean[] prime;
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(); // 최소값
        int N = sc.nextInt(); // 최대값

        prime = new boolean[N + 1]; // 0 ~ N
        makePrime();

        for(int i=M; i<=N; i++){
            if (!prime[i]){ // false => 소수
                System.out.println(i);
            }
        }

    
    }

    // 에라토스테네스의 체 알고리즘 (소수 구하기)
    public static void makePrime(){

        prime[0] = prime[1] = true; // 0, 1 소수X

        for(int i=2; i<=Math.sqrt(prime.length); i++){
            if(prime[i] == true) {continue;} // 이미 소수X => skip
            for(int j=i*i; j<prime.length; j+=i){ // 소수의 배수 => 소수X
                prime[j] = true;
            }
        }
    }

}

** "한번 구해진 소수의 배수들은 소수가 될 수 없다." 는 전제가 중요

 

참고 문헌

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

https://st-lab.tistory.com/84

[백준] 1929번 : 소수 구하기 - JAVA [자바]

---

5단계 : 4948번 / 베르트랑 공준

import java.util.Scanner;

public class Main{

    public static boolean[] prime;
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int n = -1;
        while(true){
            n = sc.nextInt();
            if (n == 0){break;}

            int count = 0;
            prime = new boolean[2*n + 1]; // 0 ~ 2n
            makePrime();

            for(int i=n+1; i<=2*n; i++){
                if (!prime[i]){ // false => 소수
                    count ++;
                }
            }
            System.out.println(count);
        }

    
    }

    public static void makePrime(){

        prime[0] = prime[1] = true; // 0, 1 소수X

        for(int i=2; i<=Math.sqrt(prime.length); i++){
            if(prime[i] == true) {continue;} // 이미 소수X => skip
            for(int j=i*i; j<prime.length; j+=i){ // 소수의 배수 => 소수X
                prime[j] = true;
            }
        }
    }

}

---

6단계 : 9020번 / 골드바흐의 추측

import java.util.Scanner;

public class Main{

    public static boolean[] prime;
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int k = 0; k<T; k++){
            int n = sc.nextInt();

            prime = new boolean[n + 1]; // 0 ~ n
            makePrime();

            int index = 0;
            while (true){
                if (!prime[n/2]){ // n/2가 소수라면 n/2 + n/2 = n 이므로 출력
                    System.out.println(n/2+" "+n/2);
                    break;
                } else {
                    index ++;
                    // n/2-index 와 n/2+index가 모두 소수인 경우
                    if( (!prime[n/2 - index]) && (!prime[n/2 + index]) ){
                        System.out.println((n/2 - index)+" "+(n/2 + index));
                        break;
                    }
                }
            }
        }    
    }

    public static void makePrime(){

        prime[0] = prime[1] = true; // 0, 1 소수X

        for(int i=2; i<=Math.sqrt(prime.length); i++){
            if(prime[i] == true) {continue;} // 이미 소수X => skip
            for(int j=i*i; j<prime.length; j+=i){ // 소수의 배수 => 소수X
                prime[j] = true;
            }
        }
    }

}

** n/2가 소수인 경우) n/2 , n/2 골드바흐 파티션 곧바로 출력

** n/2로 부터 같은 값 만큼의 +/-가 모두 소수인 경우) n/2 -index , n/2 + index 골드바흐 파티션 출력

---