[백준/JAVA] 단계별로 풀어보기(8단계) 기본 수학 2

문제 1978) 소수 찾기

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

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());
        boolean num[] = new boolean[1001];
        num[1] = true;
        for(int i=2;i<=1000;i++) {
            if(num[i])
                continue;
            for(int j=i*2;j<=1000;j+=i) {
                num[j] = true;
            }
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count =0;
        for(int i=0;i<N;i++) {
            int t = Integer.parseInt(st.nextToken());
            if(!num[t])
                count++;
        }
        System.out.println(count);
    }
}

문제 2581) 소수

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        boolean num[] = new boolean[10001];
        num[1]= true;
        int min = -1;
        int sum = 0;
        for(int i=2;i<=10000;i++) {
            if(num[i]) continue;
            for(int j=i*2;j<=N;j+=i) {
                num[j] = true;
            }
        }
        for(int i=M;i<=N;i++) {
            if(!num[i]) {
                if(min==-1) {
                    min = i;
                }
                sum+=i;
            }
        }
        if(min==-1) {
            System.out.println(min);
        }
        else {
            System.out.println(sum);
            System.out.println(min);
        }
    }
}

문제 11653) 소인수분해

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        if(num==1) {
            return;
        }

        StringBuilder sb = new StringBuilder();
        for(int i=2;i<=num;i++) {
            if(num%i==0) {
                sb.append(i).append("\n");
                num/=i;
                i--;
            }
            if(num==1)
                break;
        }
        System.out.print(sb);
    }
}

문제 1929) 소수 구하기

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean num[] = new boolean[1000001];
        StringBuilder sb = new StringBuilder();

        num[1] = true;
        for(int i=2;i<=1000;i++) {
            if(num[i]) continue;
            for(int j=i*2;j<=1000000;j+=i) {
                num[j] = true;
            }
        }
        for(int i=M;i<=N;i++) {
            if(!num[i])
                sb.append(i).append("\n");
        }
        System.out.print(sb);
    }
}

문제 4948) 베르트랑 공준

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean num[] = new boolean[123456*2+1];
        num[1] = true;
        for(int i=2;i<=Math.sqrt((double)123456*2);i++) {
            if(num[i]) continue;
            for(int j=i*2;j<=123456*2;j+=i) {
                num[j] = true;
            }
        }
        StringBuilder sb = new StringBuilder();
        String input;
        while(!(input=br.readLine()).equals("0")) {
            int n = Integer.parseInt(input);
            int count = 0;
            for(int i=n+1;i<=2*n;i++) {
                if(!num[i]) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }
        System.out.print(sb);
    }
}

문제 9020) 골드바흐의 추측

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

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());
        StringBuilder sb = new StringBuilder();
        boolean num[] = new boolean[10001];
        num[1] = true;
        for(int i=2;i<=100;i++) {
            if(num[i]) continue;
            for(int j=i*2;j<=10000;j+=i) {
                num[j] = true;
            }
        }
        for(int i=0;i<T;i++) {
            int input = Integer.parseInt(br.readLine());
            for(int j=input/2;j>=1;j--) {
                if(!num[j] && !num[input-j]) {
                    sb.append(j).append(" ").append(input-j).append("\n");
                    break;
                }
            }
        }
        System.out.print(sb);
    }
}