소수 판정 17

[백준 27172] 수 나누기 게임 [Java]

풀이 N명의 플레이어가 가진 카드에 대해서 서로 다른 플레이어의 카드 간 배수가 존재하는지 판별하는 문제다. 문제에서 두 번 이상 등장하는 카드는 없다고 하니 해당 번호의 카드의 존재여부를 기록해두면 쉽게 풀이할 수 있다. N명의 player에 대해 카드 번호를 입력받고 i번째 플레이어가 가진 카드가 있다고 표시해주자. 그 다음에는 N명의 player가 가진 카드의 배수에 해당하는 카드가 있는지 확인해주면 된다. 만약 카드 숫자가 i 일 때 카드 숫자가 j 인 카드가 있다면, j % i == 0 즉 j는 i의 배수다. 만약 최대 숫자 1,000,000 (SIZE - 1) 에 대해 i 배수를 탐색했는데 만족하는 카드가 없다면, i 카드를 가진 player는 점수를 얻을 수 없다. 점수를 score 배열에 ..

[백준 2904] 수학은 너무 쉬워 [C]

풀이 난이도에 비해 생각할 내용이 좀 많은 문제였다. 점수를 계산할 수들을 소수로 나누고 곱하는 과정을 통해 가장 큰 점수를 알아내는 문제이다. 즉, 입력받는 수들을 소인수분해하고, N개의 수들이 가장 큰 gcd값을 가지도록 소인수를 재분배하는 문제이다. 1e6까지의 78,498개의 소수들을 구하고, 입력받은 num에 대해 소인수분해를 하면서 소인수의 개수를 세주어야 한다. 다음의 예제를 보자. 8 = 2*2*2 24 = 2*2*2 *3 9 = 3*3 일때, N개의 수에 대해 2는 6개, 3은 3개가 존재한다. 이때 N = 3개의 수에 대해 각 수가 가져야할 인수들의 평균 개수는 2는 2개(6/N), 3은 1개(3/N)이므로, N개의 수들이 인수를 2*2*3으로 가질때가 가장 큰 gcd값이다. 문제에서 ..

[백준 5615] 아파트 임대 [C]

동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 2^31-1이하인 양의 정수이다.출력첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다...

[백준 2023] 신기한 소수 [C]

풀이 8자리수의 소수를 확인하기 위해 1e8만큼의 공간을 할당하면 메모리 제한에 막힌다. 심지어 조건에 맞는 모든 소수의 개수가 100개도 안된다. 때문에, 다음과 같은 규칙을 찾아 문제를 해결했다. N의 자릿수는 2, 3, 5, 7 이어야 한다. 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만 탐색해야 한다. 소스코드 #include #include int prime(int num){ int sq = sqrt(num); for (int i = 2; i

[백준 1963] 소수 경로 [C]

풀이 네 자리 수를 하나씩 바꾼 수가 소수이면서, 중복을 피하기 위해 기존에 확인한 수가 아닌 경우에만, Queue에 담아주고, 자리수를 바꾸기 전의 수의 변환 횟수에 1을 더한 값을 자리수를 바꾼 후 숫자의 변환 횟수에 입력해주었다. 소스코드 #include #include #include #include #define MAX 10000 bool cNum[MAX]; int cnt[MAX], queue[MAX]; void bfs(int old, int pw){ int front = -1, rear = -1, n; cnt[queue[++rear] = old] = 0; while (front < rear){ if ((n = queue[++front]) == pw) return; for (int i = 0; ..

[백준 1990] 소수인팰림드롬 [C]

풀이 "백준 1747, 소수&팰림드롬"와 비슷한 문제다. 입력받은 a~b에 존재하는 팰림드롬 소수를 출력해주면된다. 단, 9,989,899 이후로 1e8까지는 팰림드롬 소수가 없기 때문에 범위에서 제한해주면 된다. 소스코드 #include #include #include #include #define MAX 9989900 bool cNum[MAX] = {0, 1}; int main(){ int sq = sqrt(MAX); for (int i = 2; i = MAX && (b = MAX-1); for (int i = a; i

[백준 1747] 소수&팰림드롬 [C]

풀이 에라토스테네스의 체로 소수가 아닌 수들을 찾고, 입력받은 N부터 소수인 수들중에 팰림드롬인지 확인해서 맞으면 해당 수를 출력하고 탐색을 종료하면 된다. 단, 98689 이후의 수들이 갖는 최소의 펠림드롬 소수는 1003001이므로 예외처리를 해주어야 한다. 소스코드 #include #include #include #include #define MAX 1000001 bool cNum[MAX] = {0, 1}; int main(){ int sq = sqrt(MAX); for (int i = 2; i 98689) puts("1003001"); else for (int i = N; i < MAX; i++) if (!cNum[i]){ char str[7]; sprintf(str, "%d", i); int l..

[백준 1153] 네 개의 소수 [C]

풀이 "백준 6588, 골드바흐의 추측" 코드를 이용해 풀이했다. 단, 골드바흐의 추측은 짝수인 N에 대해 해당하기 때문에, 입력받은 N이 홀수인 경우 2, 3을, 짝수인 경우 2, 2를 먼저 출력해준 후 출력해준 수 만큼 빼준 N값에 대해 골드바흐의 추측을 사용해 풀이할 수 있다. 단, 8인 경우에는 2, 2, 2, 2이기 때문에 따로 써주거나 더 안정적인 골드바흐의 추측 알고리즘을 사용하면 된다. 소스코드 #include #include #include #define MAX 1000001 bool Cnum[MAX]; int main(){ int sq = sqrt(MAX); for (int i = 2; i