공부하는 도비

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 7은 1×7 또는 7×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 7은 소수이다. 따라서, 1과 자기자신을 제외한 수로 나눠진다면 그 수는 소수가 아니다. 이 점을 이용하여 소수를 계산해보려고 한다. #include void prime(int a) { for(int i = 1; i

암호학에서 소수는 상당히 많이 사용된다. 앞으로 소수와 관련된 내용을 정리하며, 암호에 대한 중요한 개념을 다뤄보려고 한다. * 소수 : 하나의 양정수가 오직 1이나 자신으로만 나누어 떨어진다는 말과 동일하다. → 소수와 관련된 몇가지 사실 1) 가장 작은 소수는 2이다. - Proof) 2는 1과 2로만 나누어 떨어지기 때문이다. 2) 1은 소수가 아니다. - Proof) 소수는 서로 다른 두 개의 정수로만 나누어 떨어져야 하고, 그 이상이나 그 이하의 정수로 나누어져서는 안된다. 1은 오직 자신에 의해서만 나누어지기 때문에 1은 소수가 아니다. 3) 소수는 무한하다. - 소수가 무한하다는 증명은 몇 가지가 있는데, 가장 유명한 유클리드의 증명을 살펴보기로 한다. 우선, 소수가 유한하다고 가정한다. *..

오늘은 간단한 코드 하나를 소개해볼까 합니다. 유클리드 알고리즘은 두 정수의 최대공약수를 쉽게 계산할 수 있도록 하는 것입니다. (자세한 유클리드 알고리즘의 설명은 위키피디아를 참고해주세요.) # Euclidean Algorithm import sys a, b = map(int, sys.stdin.readline().split()) print(" ") q, r = 0, 0 while(True): if a < b : a, b = b, a # swap q = a // b r = a - (q*b) print(a ,'=', q, '*', b, '+', r) if r == 0: print("\ngcd = ", b) if b == 1: print("relatively prime") break a = b b = r ..