11653 소인수분해

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;

public class Main{
    //1~a까지의 수들의 소수 판별여부를 배열로 return해주는 함수
    public static ArrayList<Integer> decimal(int a){
        //소수여부를 판별해줄 배열생성,
        boolean[] isDecimal = new boolean[a+1];
        //소수인수들만 list에 추가해서 list순서대로, 차례대로 주어진 수를 소인수분해할것임
        ArrayList<Integer> list = new ArrayList<>();
        //일단 true로 세팅해놓고 기본값들을 아래에서 세팅해준다. 이 값들은 밑의 for문의 예외가되는값이다
        for(int i=0;i<=a;i++){
            isDecimal[i] = true;
        }
        //0인경우 계속 더해봤자 0이기때문에 아래 for문으로 적용될수없다. 그리고 0 은 소수가 아니다
        isDecimal[0] = false;
        //1은 소수가 아니며, 1을 계속더하면 모든수가 false가 된다
        isDecimal[1] = false;
        //내부for문에서는 두번째꺼부터 시작되고, i=2부터시작하기때문에 2의 기본값을 세팅해주어야한다
        isDecimal[2] = true;
        //a의 제곱근까지만 돌아도 되는 이유는 a가 소수가 아니라면,
        // a = xy로 표현될수있고, x와 y는 짝을 이룬다. 대칭적인 구조를 이룬다.
        // 그렇기때문에 제곱근까지만 체크를 해도 제곱근보다 큰 범위에 대해서는 그이전에 대칭적인 구조에 의해 false로 checking이 되어있을 것이다
        for(int i=2;i<=Math.sqrt(a);i++){
            // 소수가 아닌수에 대해서는 for문을 돌지 않아도된다.
            // 소수가 아닌수는 그 수를 소인수 분해한 또다른 수에 의해 checking이 됐을것이기때문이다
            if(isDecimal[i]){
                //해당 수가 i라고 하면 i*2부터 시작해서 i*2,i*3,i*4...하나씩 숫자를 늘려나간다. 즉, i를 하나씩 더 더해준다
                //이 덧셈은 이 덧셈한 값이 a라는 값보다 같거나 작을때까지 반복한다. 자신보다 큰수가 인수일린 없으니
                for(int j=i+i;j<=a;j+=i){
                    isDecimal[j] = false;
                }
            }

        }
        //배열에 담긴 값을 list로 변환하는 과정을 거친다
        for(int i=0;i<=a;i++){
            if(isDecimal[i]) list.add(i);
        }
        return list;
    }
    public static void toPrimes(int a){
        //만약a<2인경우 decimal메서드에서 index초과배열 error가 난다 그부분을 생각해서 예외처리를 해준다
        if(a<2){
            return;
        }
        //예외처리
        if(a==2){
            System.out.println(2);
            return;
        }
        //decimal 메서드로 1~a까지숫자들중에 소수인것들만 불러온다
        ArrayList<Integer> isDecimal = decimal(a);
        //나머지를 담을 변수 result를 선언한다.
        int result;
        //소수들에 대해서만 반복문을 돌린다.
        for(int i=0;i<isDecimal.size();i++) {
            //숫자 하나를 꺼내와서 그 숫자에 대해서
            int dec = isDecimal.get(i);
            //이 숫자로 나눴을때 더이상 0이 안나올, 그러니까 그 수를 더이상의 인수로 가지지 않을때까지 계속해서 반복문을 돌린다
            result = a % dec;
            //나머지를 result에 저장한다 나머지가 0이라는것은 그 수로 나뉘어진다는얘기. 그러면 계속 나누어야한다
            if(result == 0){
                //나머지가 0인경우에는 계속해서 나눈다
                while(result == 0){
                    //나눠서 0 이 되는경우. 그 수가 인수로 존재한다는거니 그 수를 출력한다 dec은 소수인 인수를 의미한다
                    System.out.println(dec);
                    //a:parameter를 저장하는 변수이자, 매번 소인수에 의해 나눠진 몫을 저장하는 변수
                    a = a / dec;
                    //result는 나머지를 저장하여 0인경우에는 계속 반복문돌도록 한다
                    result = a % dec;

                }
            }
        }


    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        toPrimes(n);

    }


}

9020 골드바흐추측

처음시도

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;

public class Main{
    //1~a까지의 수들의 소수 판별여부를 배열로 return해주는 함수
    public static ArrayList<Integer> decimal(int a){
        //소수여부를 판별해줄 배열생성,
        boolean[] isDecimal = new boolean[a+1];
        //소수인수들만 list에 추가해서 list순서대로, 차례대로 주어진 수를 소인수분해할것임
        ArrayList<Integer> list = new ArrayList<>();
        //일단 true로 세팅해놓고 기본값들을 아래에서 세팅해준다. 이 값들은 밑의 for문의 예외가되는값이다
        for(int i=0;i<=a;i++){
            isDecimal[i] = true;
        }
        //0인경우 계속 더해봤자 0이기때문에 아래 for문으로 적용될수없다. 그리고 0 은 소수가 아니다
        isDecimal[0] = false;
        //1은 소수가 아니며, 1을 계속더하면 모든수가 false가 된다
        isDecimal[1] = false;
        //내부for문에서는 두번째꺼부터 시작되고, i=2부터시작하기때문에 2의 기본값을 세팅해주어야한다
        isDecimal[2] = true;
        //a의 제곱근까지만 돌아도 되는 이유는 a가 소수가 아니라면,
        // a = xy로 표현될수있고, x와 y는 짝을 이룬다. 대칭적인 구조를 이룬다.
        // 그렇기때문에 제곱근까지만 체크를 해도 제곱근보다 큰 범위에 대해서는 그이전에 대칭적인 구조에 의해 false로 checking이 되어있을 것이다
        for(int i=2;i<=Math.sqrt(a);i++){
            // 소수가 아닌수에 대해서는 for문을 돌지 않아도된다.
            // 소수가 아닌수는 그 수를 소인수 분해한 또다른 수에 의해 checking이 됐을것이기때문이다
            if(isDecimal[i]){
                //해당 수가 i라고 하면 i*2부터 시작해서 i*2,i*3,i*4...하나씩 숫자를 늘려나간다. 즉, i를 하나씩 더 더해준다
                //이 덧셈은 이 덧셈한 값이 a라는 값보다 같거나 작을때까지 반복한다. 자신보다 큰수가 인수일린 없으니
                for(int j=i+i;j<=a;j+=i){
                    isDecimal[j] = false;
                }
            }

        }
        //배열에 담긴 값을 list로 변환하는 과정을 거친다
        for(int i=0;i<=a;i++){
            if(isDecimal[i]) list.add(i);
        }
        return list;
    }
    public static void bach(int x){
        //소수들의 리스트
        ArrayList<Integer> decimalList = decimal(x);
        int s = decimalList.size()/2;
        int e = s+1;
        //
        while(s<e){
            int sum = decimalList.get(s) + decimalList.get(e);
            if(sum==x) {
                System.out.println(s + " " + e);
                return;
            }
            else if(sum > x) {
                if(s>0) s--;
                else e--;
            }
            else if(sum < x) {
                if(e<decimalList.size()) e++;
                else s++;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            int a = Integer.parseInt(br.readLine());
            bach(a);
        }
    }
}

두번째 시도(정답)

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;

public class Main{
    //1~a까지의 수들의 소수 판별여부를 배열로 return해주는 함수
    public static boolean[] decimal(int a){
        //소수여부를 판별해줄 배열생성,
        boolean[] isDecimal = new boolean[a+1];
        //소수인수들만 list에 추가해서 list순서대로, 차례대로 주어진 수를 소인수분해할것임
        ArrayList<Integer> list = new ArrayList<>();
        //일단 true로 세팅해놓고 기본값들을 아래에서 세팅해준다. 이 값들은 밑의 for문의 예외가되는값이다
        for(int i=0;i<=a;i++){
            isDecimal[i] = true;
        }
        //0인경우 계속 더해봤자 0이기때문에 아래 for문으로 적용될수없다. 그리고 0 은 소수가 아니다
        isDecimal[0] = false;
        //1은 소수가 아니며, 1을 계속더하면 모든수가 false가 된다
        isDecimal[1] = false;
        //내부for문에서는 두번째꺼부터 시작되고, i=2부터시작하기때문에 2의 기본값을 세팅해주어야한다
        isDecimal[2] = true;
        //a의 제곱근까지만 돌아도 되는 이유는 a가 소수가 아니라면,
        // a = xy로 표현될수있고, x와 y는 짝을 이룬다. 대칭적인 구조를 이룬다.
        // 그렇기때문에 제곱근까지만 체크를 해도 제곱근보다 큰 범위에 대해서는 그이전에 대칭적인 구조에 의해 false로 checking이 되어있을 것이다
        for(int i=2;i<=Math.sqrt(a);i++){
            // 소수가 아닌수에 대해서는 for문을 돌지 않아도된다.
            // 소수가 아닌수는 그 수를 소인수 분해한 또다른 수에 의해 checking이 됐을것이기때문이다
            if(isDecimal[i]){
                //해당 수가 i라고 하면 i*2부터 시작해서 i*2,i*3,i*4...하나씩 숫자를 늘려나간다. 즉, i를 하나씩 더 더해준다
                //이 덧셈은 이 덧셈한 값이 a라는 값보다 같거나 작을때까지 반복한다. 자신보다 큰수가 인수일린 없으니
                for(int j=i+i;j<=a;j+=i){
                    isDecimal[j] = false;
                }
            }

        }
        return isDecimal;
    }
    public static void bach(int x){
        //소수들의 리스트
        boolean[] decimal = decimal(x);
        //더해서 a를 만들어야하고, 두수의 차이가 가장적기 위해서는 둘다 절반으로 setting
        int a = x/2;
        int b = x/2;
        //조건이 부합할때만 break하고 출력하도록. 어차피 어쩌고원리에따라 break분을 만나게 되어있음
        while(true){
            //더해서 x가 돼야하고 둘다 소수여야한다
            if(a+b==x && decimal[a] && decimal[b]){
                //출력
                System.out.println(a + " " + b);
                //while문 탈출, 함수 종료
                return;
            }
            //a는 하나줄고
            a -= 1;
            //b는 하나 더해서 총합을 x로 유지시키면서 둘의 차이를 최소로한다
            b += 1;

        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            int a = Integer.parseInt(br.readLine());
            bach(a);
        }

    }


}

6588: 골드바흐추측2

코드1

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;

public class Main{
   //dicimal은 위와 동일
     public static void bach2(int x){
        //매번 x이하의 소수인지의 여부를 불러와본다
        boolean[] isDecimal = decimal(x);
        //가장 작은 홀수이자소수는 3이다
        int a = 3;//홀수 대입
        //입력으로는 4이상의 숫자가 들어올것이다
        int b = x-3;//짝수-홀수 = 홀수
        //절반까지만 돌아도되기때문에 a<=b의조건을두었다. 둘의 순서가 바뀌어진다는것은 곧 저 골드바흐어찌구가 틀렸다는 의미이다.
        while(a<=b){
            //둘다 소수이고, 둘이 더해서 x가 되는 순간 출력해버린다
            if(isDecimal[a]&&isDecimal[b]&&a+b==x){
                //출력
                System.out.println(x +" = " + a + " + " + b);
                //함수를 끝낸다
                return;
            }
            //홀수를만들어야하고, 둘이더해서 x를 만들어야하기에 같은수를 뺴주고, 홀수를만들어야하니까 2를빼준다
            a +=2;
            b -=2;
        }
        //a>b가되는순간 골드바흐는 틀리게되는것이다. 범주내에 조건을 만족하는 a,b가없다는뜻
        System.out.println("Goldbach's conjecture is wrong.");
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        while(n!=0){
            //입력이0이아닌경우에만 계속해서 입력을받을것이고, 함수를실행시킬것이다
            if(n>=4&&n%2==0){
                //입력조건에 맞는경우만 이 메서드를실행한다.지금생각해보면 필요없는조건이라고 생각한다
                bach2(n);
                //n이 아닌 수를 입력받아서 그 입력에 대한 출력을 하고 나서 또 입력을 받는다
                n = Integer.parseInt(br.readLine());
            }
            else{
                System.out.println("Goldbach's conjecture is wrong.");
            }

        }

    }

코드2

입력을받을때마다 매번 x이하의 수에서 소수를 판별하는것이 오래걸린다. 일단 1000000이하의 소수를 구해놓은 다음에
판별한다. 여러번입력이 들어올경우 이런식으로 한번에 큰 범위의 for문을 돌아버린다음에 그 정보가지고 해결을하면 시간이 확 단축되는것같다

 public static void bach2(int x, boolean[] isDecimal) throws IOException {

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int a = 3;//홀수 대입
        int b = x-3;//짝수-홀수 = 홀수
        while(a<=b){
            if(isDecimal[a]&&isDecimal[b]){
                bw.write(x +" = " + a + " + " + b + "\n");
                bw.flush();
                return;
            }
            a +=2;
            b -=2;
        }
        bw.write("Goldbach's conjecture is wrong.\n");
        bw.flush();
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        boolean[] isDecimal = decimal(1000000);

        while(n!=0){
            if(n>=4&&n%2==0){
                bach2(n, isDecimal);
                n = Integer.parseInt(br.readLine());
            }
            else{
                bw.write("Goldbach's conjecture is wrong.\n");
                bw.flush();
                bw.close();
            }

        }

    }

질문

여러개의 입력이 들어오는건 시간복잡도 계산을 어떻게하는건가?
내가 입력을 최대 100000개를 하고 한번당 연산이 100000번들으면 그냥곱하면 되는건가? 근데.. 저거보면
o(n)이라고만 쳐도 곱하면 1억넘어가는데.. 뭐지..?
어떻게계산하는거지?