1. 문제 16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 500만 이내의 값에 대한 100만개의 수가 주어질때 각각을 소인수분해하는 문제 2. smallest prime factor smallest prime factor 알고리즘은 어떤 수의 가장 작은 소인수를 찾아 배열에 저장하는 알고리즘이다. 소인수분해를 수행하는 기본 알고리즘은.. p = 2부터 시작해서 $\sqrt{n}$까지 나눠보면서 소인수를 찾는데 #trivial prime factorizatio..
1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$이다. 1-2) p가 소수이면, 모든 정수 a에 대하여 $$a^{p} \equiv a (mod p)$$ 응용하는 방법은 여러가지가 있겠지만, 하나하나 다 나열할 수도 없고, 접한지 얼마 안되었으니 나도 다 모르고 증명도 굳이 할 필요없을 것 같고, 받아들이면서 문제를 풀면서 익혀보기로 하자 2. 응용 - 합성수 판정 페르마의 소정리 역은 성립하지 않는다. 즉, a와 p가 서로소일때, $$a^{p-1} \equiv 1 (mod p)$$가 성립한다면, p는 소수이다는 거짓이다. 즉, ..
1. 문제 11653번: 소인수분해 (acmicpc.net) 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 2. 소인수분해 하는 방법? 어렵게 생각할 필요 없이 사람이 소인수 분해를 어떻게 하는지 생각해보자. 100을 소인수분해 한다고 해보자. 암산으로 5*20 >>> 5*4*5 >> 5^2 * 2^2이 나오기는 하는데... 이게 어떻게 이루어지는가??? 처음부터 생각해보자. 소인수분해는 소수들의 곱이다. 그러니까 소수의 최솟값인 2부터 시작해서 주어진 수 100을 나눠보면 된다. 만약에 100이 2로 나누어진다면? 100 = 2 * 50이다. 그러면.. 우리는 어떤 걸 이제 나누어보는가? 100을 2로 나누고 나온 몫인 50을..
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. 문제 https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수가 몇개 인지 알아보려 합니다. 0P0 처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
