★ 「2019학년도 1학기」 수/업/노/트 ★
by. 동동매니저 >_<
▶ 일자 : 2019년 03월 25일 (월)
▶ 과목 : 이산수학
▶ 담당 교수님 : SCH 컴소공 박두순 교수님
※ 이번 수업의 핵심 키워드!!
소수
메르센 수
※ 수업 내용을 요약해보면?
▶ 소수(Prime Number) : 약수가 1과 자기 자신만 있는 수
▶ 메르센 수 : 2n-1 형태의 수
▶ 메르센 소수 : 메르센 수 중 소수인 수
– 현재까지 알려진 메르센 소수 중 가장 큰 수 = 277232917-1이며, 약 2300만 자리를 차지함.
☆ 소수 구하는 가장 빠른 법!!
N이 소수인지 판별하기 위해서는, 2~sqrt(N) 범위의 모든 소수로 나누어 떨어지지 않으면 소수라고 판정할 수 있음.
(합성수의 약수를 일렬로 세우면, sqrt(N)을 중심으로 같은 거리만큼 떨어진 수끼리 곱하면, N이 됨(좌우 대칭).)
▶ 예시 : 36의 약수 = 1, 2, 3, 4, 6, 9, 12, 18, 36
▶ sqrt(N) = 6
▶ 6*6 = 4*9 = 3*12 = 2*18 = 1*36 = 36
※ 수업을 듣고 나서 느낀 점!!
메르센 소수를 구해보고 싶다는 생각도 들었지만, 수가 어마어마하게 큰 수여서 엄두를 내지 못할 것 같음.
이 내용을 듣고, Java의 BigInteger 클래스를 떠올렸고, 이를 속도가 빠른 C언어로도 구현해보고 싶다는 생각도 들었음.
(언젠간 가능하겠죠?)
※ 기타 참고 사항!!
없음