1. 소수를 구하는 방법 컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다. n의 약수가 1과 n만 있어야 n이 소수이다. #숫자 n이 소수이면 True, 아니면 False #단 1은 소수가 아니다 def is_prime(n): if n == 1: return False else: for i in range(2,n): #1과 n으로는 당연히 나누어 떨어지니까, 2~n-1까지 검사 if n % i == 0: return False return True 2. 에라토스테네스의 체 2-1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2-2) 2를 제외한 2의 배수를 모두 지운다 2-3) 3을 제외한 3의 배수를 모두 ..
1. 페르마의 소정리 p가 소수이면 모든 정수 a에 대하여 $a^p$와 a를 p로 나눈 나머지는 서로 같다. 만약 a가 p의 배수가 아닌 서로소라면 $a^{(p-1)}$와 1을 p로 나눈 나머지는 서로 같다 역은 성립하지 않는다. 즉 모든 정수 a에 대하여 $a^p \equiv a (mod p)$임에도 불구하고 p가 합성수일 수 있다 2. 응용 - 이항계수를 빠르게 구하는 방법 n과 r이 10만에서 100만정도 되는 매우 큰 수에 대하여 어떻게 하면 빠르게 구할 수 있을까 파스칼의 삼각형을 이용한 다이나믹 프로그래밍으로는 이제는 불가능하다 그래서 $nCr = n! / ((n-r)! * r!)$을 직접 구할 필요가 있는데 이 경우 n과 r이 매우 크면 직접 나타내기 어려우므로 어떤 소수 p에 대해 나머지를..
1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰 약수를 최대공약수라고 부른다. 중요한 성질중 하나는 최대공약수의 약수는 a,b의 공약수이다. 2. 유클리드 호제법 두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( r은 0이상 b 미만)이라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다. 즉, gcd(a,b) = gcd(b,r)이다. 만약 r=0이라하면, a,b의 최대공약수는 b이다. 3. 유클리드 호제법 활용 단 1번만 사용해서는 그 진짜 힘을 알 수 없다. a = bq + r이면 a,b의 최대공약수는 b,r의 최대공약수와 같다 b를 r로 나눠서 b = rq2 + r2라는 식을 얻는다면, 결국 b,r의 최대공약수는 r,r2의 최대공약수와 같다. 여기서 r을..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이조각으로 만들 수 있는 소수가 몇개인지 return하도록 solution 함수를 완성해주세요. 2. 제한사항 numbers는 길이 1 이상 7..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
