0과 1의 쉼터

풀이 에라토스테네스의 채로 소수가 아닌 수들을 먼저 구한 후 풀이를 했다. 두 수의 합이 N과 같고, 두 수가 소수인경우에만 반복문을 종료해 답을 출력해주면 된다. 소스코드 #include #include #include #define MAX 1000001 int main(){ int sq = sqrt(MAX-1); bool not_prime[MAX] = {0,}; for (int i = 2; i

소스코드 #include #include #define MAX 1001 bool not_prime[MAX]; int main(){ int N, K; scanf("%d %d", &N, &K); for (int i = 2; i

풀이 연속된 소수의 합이므로, 소수로만 이루어진 배열에서 투 포인트를 적용하면 된다. 에라토스테네스의 체로 소수가 아닌 것들을 구분하여 소수로만 이루어진 배열을 만들고, 투 포인트 방식으로 풀이했다. 소스코드 #include #include #include #define MAX 4000001 bool not_prime[MAX]; int sum_prime[MAX/10]; int main(){ int N; scanf("%d", &N); int sq = sqrt(N); for (int i = 2; i

풀이 위의 예제는 다음과 같은 규칙이 있다. gcd(1, 소수) = 1 이므로 계산할 필요가 없으며, gcd(소수, 소수) = 소수 이다. gcd(N, M) = K일 때, gcd(N + K*i, M + K*i)는 모두 K이다. (단, i = 2~N or M) 위의 조건에서 얻은 K는 K의 제곱수가 존재할 경우 변경된다. N과 M크기를 이용해 K의 개수를 구할 수 있다. 두번째 조건에서 얻은 K들의 곱들과 세번째 조건에서 얻은 수의 중복을 피해야 한다. 다음과 같이 p+K*i (단, i = 0 ~ (p+K*i

문제 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력 첫째 줄에 두 정수 min과 max가 주어진다. 출력 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. 제한 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 풀이 문제에서 주어진 "제곱 ㄴㄴ 수"는 수론에서 제곱 인수가 없는 정수(Square-free Integer)로, 1이 아닌 제곱수를 인수로 지 않는 양의 정수이다. 쉽게 정수에 대해 소인수분해를 했을 때 동일한 글에서..

풀이 "백준 1978 소수 찾기"문제와 유사하다. 단, 1은 소수가 아니다 arr[0] = 0으로 초기화해주자. 소스코드 #include #include #define MAX 1000000 int arr[MAX]; int main(){ int idx = 3; for (int i = 0; i < MAX; i++) arr[i] = i+1; for (int i = 2; i

풀이 입력받은 수 num이 num/2 이하의 범위 중에 소수가 존재하는지 몇 줄 내로 간단하게 해결할 수 있지만, 에라토스테네스의 체를 이용해 효율적으로 풀이해봤다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 알고리즘이다. N까지의 수는, N의 제곱근보다 작은 정수들의 배수를 모두 지우고 남는 수가 소수라는 사실을 알 수 있다. 이번 문제에서 주어지는 최대의 자연수는 1000으로, 1000의 제곱근인 31.62xxx보다 작은 정수 31까지의 배수들을 제외하고 남은 수들이 소수임을 알 수 있다. 하지만, 문제에서 입력받는 수가 소수인지 확인하기 위해 탐색하는 과정이 효율적이지 못해 위에서 조작한 배열을 소수와 소수가 아닌 구간으로 정렬해주었다. int arr[MAX], ..