알고리즘/수학
-
[백준 4948]-[수학] - 베르트랑 공준알고리즘/수학 2018. 11. 27. 14:34
문제링크 : https://www.acmicpc.net/problem/4948 이 문제는 에라토스테네스의 체를 이용해서 푸는 좀 심화 문제라고 생각하면 된다. 2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java) 먼저 이문제를 풀기전에 입력수의 크기는 12345 라고 하고 베르트랑의 공준이 어떤 내용인지 설명해주고 있다. n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 배열의 범위를 123456 로만 하면 인덱스가 초과되서 런타임에러가 발생한다.최소 범위 123456 * 2 값인 246912 + 1 을 해야한다. 문제를 푸는 순서는 다음 순서를 따른다.1) 에라토스테네스의 체로 2부터..
-
[백준 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..
-
[백준-1978]-[수학-소수]-소수 찾기 (java)알고리즘/수학 2018. 11. 27. 12:33
문제링크 : https://www.acmicpc.net/problem/1978 이 문제는 입력받은 수 중에서 소수가 몇개 존재하는지 출력하는 문제이다. 먼저 소수는 1을 제외하고 1과 본인으로만 나눠질 수 있는 수를 말한다. 2부터 입력받은 수 N-1 까지 반복을 돌면서 나눈 나머지 값이 한번이라도 0이 된다면 그 수는 소수가 아니라는 소스를 만들면 된다. 이 문제에서 해줘야 하는 예외 처리는 1은 소수가 아니기 때문에 1을 입력 받으면 소수가 아니라고 판단하면 되겠다. 소스 12345678910111213141516171819202122232425262728293031323334import java.io.BufferedReader;import java.io.IOException;import java.i..