소수
-
[백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)알고리즘/수학 2018. 11. 27. 13:58
문제링크 : https://www.acmicpc.net/problem/1929 이 문제는 간단한 소수 구하기 소스로 구한다면 굉장히 오랜 시간이 걸리고 시간 초과가 발생하는 문제다. 이문제의 입력되는 수의 범위는 1 ~ 1,000,000 인데 기존 소수 구하는 방식은 2 ~ N-1 까지 반복하면서 나누어 지는 수가 있는지 판단하는 소스 였다. 그럼 최악의 상황에서 1에서 1,000,000 까지 구해야 한다면 상상할 수 없는 연산 수가 발생한다. 이렇게 큰 수들에도 소수가 있을거고 그럼 이 큰 수들을 소수인지 판별하는 방법도 있을것이다. 그게 바로 에라토스테네스의 체 라는 방식인데 노가다라 비효율적인 방식이라고는 하는데 지금 문제에는 제일 적합한 방식이다. 출처 : wiki 백과 에라토스테네스의 체를 구하..
-
[백준 2581] - [수학] - 소수알고리즘/수학 2018. 11. 27. 12:51
문제 링크 : https://www.acmicpc.net/problem/2581 이 문제는 소수이 먼저 확인하고 소수인 수를 합하고 최소값만 구하면 되는 문제이다. 입력받는 수의 최대값은 10000 이기 때문에 int 타입으로 처리가 가능하고 int 타입의 최대 수를 MIN 값으로 초기화 한 뒤에 풀면 소수일경우 최소값을 판단하는데 쉽게 판단 할 수 있다. 그리고 마지막에 결과를 반환할때 최소값의 값이 아직 int의 최대값이면 소수가 발견되지 않은거기 때문데 -1을 출력하면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOExceptio..
-
[백준-1963]-[BFS]-소수경로알고리즘/BFS_DFS 2018. 11. 23. 01:04
문제 경로 : https://www.acmicpc.net/problem/1963 이 문제는 까먹었던 소수에대해서 다시 기억하게 해준 고마운 문제다. 먼저 소수는 1 과 자신 이외에 나누어지지 않는 수를 소수라고 한다. 그럼 소수인지 아닌지 어떻게 확인할까?? N이라는 수가 있다면 2부터 N 전의 정수로 전부 나눠서 하나라도 나누어지는 값이 있다면 그것은 소수가 아니고 나누어지는 값이 없다면 그 값은 소수이다. 1은 소수가 아니다. 그래서 1은 예외처리를 해줘야 한다. 소수 판별하는 소스 12345678910111213 public static boolean isPrimeNum (int num) { boolean result = true; if(num == 1) return false; for(int i ..