소수5 [백준 6588] 골드바흐의 추측 www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 에라토스테네스의 체를 사용하여 1000000까지 소수를 체크하고 주어진 입력 t의 양끝점을 확인하여 start + end == t 가 되는 지점을 확인한다. #include using namespace std; int t; int arr[10000001]; int main(void) { for (int i = 2; i * i 2021. 1. 5. [백준 1456] 거의 소수 www.acmicpc.net/problem/1456 1456번: 거의 소수 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. A의 범위는 10^14보다 작거나 같은 자연수이고, B는 A보다 크거나 같고, 10^14보다 작거나 같은 자연수이다. www.acmicpc.net 에라토스테네스의 체를 사용하면 되지만 소수 제곱을 확인하는 과정에서 long long으로 선언해도 오버플로우가 발생한다. 예를 들어 i =10^7이고, tmp = 10^14라면 tmp * i = 10^21을 확인할 때 계산 자체가 오버플로우기 때문이다. 따라서! if( i * tmp 2020. 12. 23. [백준 1929] 소수 구하기 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 사용하여 구하면 쉽게 구한다. #include using namespace std; int m, n; bool arr[1000001] = { false, }; void eratos(int len) { arr[1] = true; for (int i = 2; i 2020. 12. 22. [백준 1978] 소수 찾기 www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 에라토스테네스의 체 개념 복습하기 에라토스테네스의 체? 2부터 시작해서 주어진 수 n까지 돌면서 배수를 체크해서 소수를 구하는 방법이다. #include using namespace std; int prime[1001]; void eratos() { prime[1] = 1; for (int i = 2; i 2020. 12. 18. 이전 1 2 다음