문제 링크 : www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 소수와 관련된 문제는 왠만하면 전부 에라토스테네스를 사용하는게 편한것 같다. 일단, 테스트케이스에서 주어진 범위만큼 에라토스테네스의 체를 사용하여 소수를 구해놓는다. 그리고 문제의 조건에 맞 게 출력해주면 끝. infinitt.tistory.com/232 알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소�� 수학과 관련한 기초문제에는 크게 3가지 분류로 ..

문제 링크 : https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 www.acmicpc.net 에라토스테네스 개념 : https://infinitt.tistory.com/232 알고리즘 (1) - 수학 : ..

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 이용하면 된다. https://infinitt.tistory.com/232 알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수) codepuls의 sw역량테스트_기초파트를 듣고 정리한 내용입니다. 수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 나머지 연산 최대 공약수, 최소 공배수 소수 (prime number) 1...

수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 나머지 연산 최대 공약수, 최소 공배수 소수 (prime number) 1. 나머지 연산 (Modular Arithmetic) Python 으로 문제를 푼다면 상관없겠지만, C++ , Java와 같은 경우에는 표현할 수 있는 정수의 길이가 제한되어있다. 가장 긴 정수 표현방법인 longlong으로 했을때 8byte이므로.... 따라서 문제에서는 이를 n으로 나눈 나머지를 구하라 와 같은 방식으로 출제하게 된다. 흔히 %를 사용하는 modular. * 이러한 유형의 문제를 풀때 알아두면 좋은 공식 덧셈 : (A+B)%C = (A%C + B%C)%C 곱셈 : (A*B)%C = (A%C * B%C)%C 뺄셈 : (A-B)%C = ((A%C)-(B%C)..