알고리즘

1번 → '에라토스테네스의 채'를 이용한 골드바흐 파티션 구하기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[] prime = new boolean[10001]; //소수 : false, 합성수 : true //전체 시간복잡도 : O(log(log(N)) //전체 공간복잡도 : O(N) public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(n..

1번 → 제곱근을 이용한 범위 내의 소수 개수 파악 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { //전체 시간복잡도 : O(sqrt(N)) //전체 공간복잡도 : 자료구조 x public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); //출력..

-번 → '에라토스테네스의 채'를 이용한 소수 판별 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[] prime; //소수 : false, 합성수 : true //전체 시간복잡도 : O(log(log(N)) //전체 공간복잡도 : O(N) public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System...

1번 ( ⌜2581번 : 소수⌟에서 사용한 방법 ) → '에라토스테네스의 채'를 이용한 소수 판별 - 저번 문제에서 사용한 '에라토스테네스의 채'를 한 번 이용해보고 싶어 작성해 보았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static boolean [] num_ary; //solve 함수에서 배열의 값이 정해지므로 static 으로 선언했다. //시간복잡도 : O(log(logN)) //1. 입력받은 정수 범위까지 소수 판별 //2. 소수만을 따로 추출 //3. 입력받은 수를 소수만으로 따로 나누어, 떨어지는 수를 String..

1번 ( ⌜1978번 : 소수 찾기⌟에서 사용한 방법 ) → 제곱근을 이용한 소수 판별 : 입력받은 Num 이 '소수' 가 아닌 '합성수' 이면 Num = X * Y 에서 X 와 Y 중 적어도 하나는 Number 의 제곱근보다 작거나 같다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { //전체 시간 복잡도 : O(N(sqrt(N))) //전체 공간 복잡도 : 자료구조 x public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..

1번 → 기본적인 소수 판별 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int count = 0; //입력 받은 수 중 전체적인 소수 개수 //전체 시간 복잡도 : O(N^2) //전체 공간 복잡도 : 자료구조 x public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 실행을 위해 버퍼..