16 삐약 : 백준 9020 [JAVA]

 

소수를 활용하는 문제이다아아아

이제 소수보면 에라토스테네스를 어떻게 적용해야 할지 머리를 열심히 굴리고 있다.

생각보다 디자인 하는 데 시간이 오래 걸리지 않았고 냅다 구현을 시작했다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.io.OutputStreamWriter;

import java.util.Scanner;

public class Main {

	static boolean[] arr ;

	public static void get_prime(int n) {

		arr = new boolean[n+1];

		arr[0]=arr[1]=true;


		for(int i=2;i*i<=n;i++) {
			if(!arr[i]) {
				for(int j=i*i;j<=n;j+=i) arr[j]=true;
			}
		}

	}

	public static void main(String ags[]){
		Scanner sc = new Scanner(System.in);

		int count =sc.nextInt();

		while(count-- >0) {

			int n = sc.nextInt();

			get_prime(n);



			int front=2;
			int temp=0;

			while(true) {

				int back = n-front;

				if(front>back) break;

				if(!arr[front] && !arr[back]) temp=front;
				
				front++;

			}
			String str = Integer.toString(temp)+' '+Integer.toString(n-temp);
			System.out.println(str);

		}
	}
}

• get_prime
  • 파라미터로 받아온 n까지의 수 중 소수를 저장하는 배열을 만드는 함수 
  • 소수일 경우 false, 소수가 아닐경우 true의 값을 가지고 있다.

 

• main
  • 작은 수와 큰 수가 모두 소수일 때 temp변수에 작은 수의 값을 저장 해 둔다
  • 이후 작은수의 범위가 큰 수보다 커졌을 때 반복문을 종료하고 두 수를 출력한다.

---

 

결과는!!!

냅다 맞았다 !!

 

 

나는 front>back으로 조건을 걸어 놨지만 신기한 방법을 하나 보았다.

 

		while (T-- > 0) {
			int n = in.nextInt();
			int first_partition = n / 2;
			int second_partition = n / 2;
 
			while (true) {
				if (!prime[first_partition] && !prime[second_partition]) {
					System.out.println(first_partition + " " + second_partition);
					break;
				}
				first_partition--;
				second_partition++;
			}
		}

이런식으로 가운데 값부터 시작하여 양 옆으로 뻗어나가면서 두 수를 찾는 방법도 있다.

출처 : https://st-lab.tistory.com/91

 

오늘도 열심히 삐약거렸구낭

삐약🐣