[알고리즘] 백준 - 1978번 : 소수 찾기 / 1929번 : 소수 구하기 / 6588번 : 골드바흐의 추측 / 17103번 : 골든바흐 파티션

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

내가 작성한 코드

import java.util.Scanner;

public class Main {
	
	public static boolean prime(int a) {
		if(a==1) {//1인 경우
			return false;
		}
		for(int i=2; i*i<=a; i++) {
			if(a % i == 0) {//약수인 경우
				return false;
			}
		}
		return true;//소수인 경우
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int answer = 0;
		for(int i=0; i<n; i++) {
			int num = sc.nextInt();
			if(prime(num)==true) {
				answer++;
			}
		}
		System.out.println(answer);
	}
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

내가 작성한 코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int m = sc.nextInt();
		int n = sc.nextInt();
		boolean[] checked = new boolean[n+1]; //소수가 아닌 경우 true
		int[] answer = new int[n-m+1]; //소수를 저장
		int index = 0; //정답을 저장할 인덱스
		for(int i=2; i<=n; i++) {
			if(checked[i]==false) {//소수일 경우
				if(m<=i) {//m보다 같거나 큰 소수부터 저장
					answer[index++] = i;
				}
				for(int j=i*2; j<=n; j+=i) {//소수의 배수들을 체크
					checked[j]=true;
				}
			}
		}
		for(int i=0; i<answer.length; i++) {
			if(answer[i]==0) {
				break;
			}
			sb.append(answer[i]+"\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		sc.close();
	}
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

내가 작성한 코드

import java.util.Scanner;

public class Main {
	
	public static boolean[] prime(int n) {
    	//에라토스테네스의 체로 소수가 아닌 것 true 표기
		boolean[] check = new boolean[n+1];
		check[0]=check[1]=true;
		for(int i=2; i<=n; i++) {
			if(check[i]==false) {
				for(int j=i*2; j<=n; j+=i) {
					check[j]=true;
				}
			}
		}
		return check;
	}
	
	public static void main(String[] args) {
		boolean[] check = prime(1000000);
		Scanner sc = new Scanner(System.in);
		int n = 0;
		while((n=sc.nextInt())!=0){
			int b = 0;
			String answer = "";
			for(int i=3; i<=n-3; i+=2) {
				/* b-a가 가장 큰 것을 출력해야 하므로
				b가 가장 큰 것을 출력(a는 가장 작은 홀수 소수인 3부터 출발) */
				b = n-i; 
				if(check[i]==false && check[b]==false) {
					answer = n+" = "+i+" + "+b;
					break;
				}
			}
			System.out.println(answer);
		}
	}
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

내가 작성한 코드

import java.util.Scanner;

public class Main {
	public static boolean[] prime(int n) {
		boolean[] check = new boolean[n+1];
		check[0] = check[1] = true;
		for(int i=2; i<=n; i++) {
			if(check[i]==false) {
				for(int j=i*2; j<=n; j+=i) {
					check[j] = true;
				}
			}
		}
		return check;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] check = prime(1000000);
		for(int i=0; i<n; i++) {
			int even = sc.nextInt();
			int answer = 0;
			for(int j=2; j*2<=even; j++) {
				if(check[j]==false && check[even-j]==false) {
					answer++;
				}
			}
			System.out.println(answer);
		}
	}
}