정수론

https://www.acmicpc.net/problem/2581 문제를 풀기 앞서,소수는 1과 자기 자신만을 약수로 가져야 한다.이전에 풀었던 소수 문제는 숫자 하나에 대해서 그 숫자가 소수인지를 판별했지만이 문제는 여러 소수를 찾는 문제이다. 여러 소수를 찾을 때는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 편하다.에라토스테네스의 체는 주어진 한계까지 모든 소수를 찾는 고대 알고리즘이다.이 방법으로 주어진 정수 N 보다 작거나 같은 모든 소수를 찾으려면2로 시작하여 2의 배수를 제외시킨다.3으로 시작하여 3의 배수를 제외시킨다. (이때 2의 배수는 통과한다.)위와 같은 방식으로 주어진 정수 N의 제곱근까지 반복한다.소수는 1과 자기 자신으로만 나눠져야 한다. 즉,..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.www.acmicpc.net 문제를 풀기 앞서,소수는 1과 자기 자신만을 약수로 가져야 한다.즉, 1과 자기 자신을 제외한 숫자를 해당 숫자에 나눠서 나온 나머지가 0이 있다면 그 수는 소수가 아니다.따라서 소수를 구하기 위해 2부터 해당 숫자 전까지의 수를 하나씩 해당 수에 나누면서 구하려고 했다. 예를 들어, 7이라는 수가 주어졌다.소수 계산결과7 % 2 = 1약수X7 % 3 = 1약수X7 % 4 = 1약수X7 % 5 = 1약수X7 % 6 = 1약수X위 표처럼 1과 자기 자신을 제외한 모든 수..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.www.acmicpc.net 문제를 풀기 앞서, 유클리드 호제법으로 구하는 방법은 그동안 알던 최대공약수, 최소공배수 방법과는 조금 다르다. - 최대공약수숫자 A, B가 있다면 두 수를 나누어서 나온 나머지가 R이라고 해보자.이때 R이 0이면 B가 최대공약수가 된다.만약 R이 0이 아니라면 A에 B를 대입하고, B에 R을 대입해서 두 수를 다시 나누는 방법을 R이 0일 될 때까지 반복한다. 100, 46을 예로 들어보자.ABresult (R)100..