펭로그

문제링크 : https://boj.kr/1929 BOJ 2581 소수 문제랑 완전 동일한 문제라고 할 수 있다.소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문..

문제 링크 : https://boj.kr/1978 이 문제는 에라토스테네스의 체를 이용하여 소수 리스트를 미리 구한다음 계산하면 쉽게 답을 찾을 수 있다.입력 최대값이 1000밖에 안되기 때문에 그냥 1000까지 미리 소수를 구하는 편이 빠른 것 같다. 12345678910111213141516171819202122232425262728293031323334#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); bool isPrime[1001]; memset(isPrime, true, sizeof(isPrime)); // 에라토스테네스의 체 이용하여 1000까지의 소수..

문제 링크 : https://boj.kr/2581 소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문에 소수 리스트를 미리 구해놓고 구하는 편이 빠른 연산 방법이..

문제링크 : https://boj.kr/11653 어떤 숫자의 소인수들은 소수들의 곱으로 표현할 수 있다.그러기 위해선 입력 숫자의 범위만큼 소수 리스트를 구해서 해당 소수들이 입력 숫자로 나누어 떨어지는지를 계산하고 이를 무한히 반복하여 더이상 나누어 떨어지지 않을 때까지 나누면 된다. 다만, 소수 리스트를 다 구할 필요는 없고 입력 숫자의 제곱근 범위까지만 구하면 된다.제곱근보다 큰 범위의 숫자를 2개 이상 서로 곱하면 입력 숫자를 초과하기 때문에 더 이상 구할 필요가 없다.소수 리스트에 속하지 않은 남은 숫자는 무조건 소수이다. (해당 숫자가 소수 리스트의 곱으로 표현되는 순간 소수가 아니다.) 소수 판별은 에라토스테네스의 체를 이용하여 구하면 더 빠르게 구할 수 있다. 123456789101112..

문제링크 : https://boj.kr/2960 시작 숫자부터 해당 숫자만큼의 배수로 탐색하여 답을 찾아가면 된다.단 한번도 특정 숫자로 나누어 떨어지지 않은 숫자는 모두 소수이고 그 소수의 배수들은 소수가 아닌 수가 된다. 소수를 구하는 알고리즘은 다음과 같다.처음으로 지워지는 숫자인 파란색은 소수이고 지워진 수는 소수의 N 배수이다. 배수가 되는 순간 소수가 아니기 때문에 당연히 파란색만 소수가 된다. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2의 배수 제거2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3의 배수 제거2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5의 배수 ..