2013/02/02 5

Pollard's rho method 소개: 정수의 인수분해(factorizing integers) with OCaml

정의 (소수와 합성수) 1보다 큰 양의 정수 n에 대하여 (i) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하면, n을 합성수(合成數, composite number)라고 한다. 참고로 이 경우, a, b 중에 적어도 하나는 sqrt(n) 보다 작거나 같다. 합성수의 예로는 4, 6, 9, 24, 143 등이 있다. (ii) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하지 않으면, 즉 n을 두 양의 정수의 곱으로 표현하는 방법이 1*n과 n*1 두 가지 뿐이면, n을 소수(素數, prime number)라고 한다. 소수의 예로는 2, 3, 5, 7, 11 등이 있다. n이 소수인지 아닌지 확인하려면, n을 2 보다 크거나 같고 sqrt(n) 보다 작거..

스트링 리스트에서 스트링 찾기(find) with OCaml

[파일명: testStringFindInList.ml]------------------------------------------------ open Printf;; let is_member arr s = List.exists (fun x -> x = s) arr ;; let findIndex s data = let rec loop s1 l acc = match l with | x::xs -> if x = s1 then acc else loop s1 xs (acc + 1) | [] -> -1 in let k = loop s data 0 in k ;; let printList data = let rec loop l = match l with | x::[] -> printf "%s" x | x::xs -> ..

스트링 배열 정렬(sorting)하기 with OCaml

printList 함수를 OCaml 의 함수형 언어의 특징을 살려 (꼬리 재귀호출과 match 표현을 이용하여) 구현하였다. [파일명: testSort.ml]------------------------------------------------ open Printf ;; let printList data = let rec loop l = match l with | x::[] -> printf "%s" x | x::xs -> begin printf "%s, " x; loop xs end | [] -> printf "" in printf "[" ; loop data ; printf "]" ;; (* Begin here *) let cmdArgs = Sys.argv in let args2 = Array.sub..

손으로 계산하는 긴자리 곱셈표 만들기 with OCaml

초등학교 때 배우던 두 정수의 곱셈표를 만들어 주는 F# 소스이다. 이 소스는 Python 소스를 F# 소스로 변환한 후 다시 OCaml 언어로 재작성한 것이라서 OCaml 의 명령형 언어 특징을 위주로 짜여져 있다. (* * Filename: makeMultTable.ml * * Print a multiplication table. * * Execute: ocaml makeMultTable.ml 123 450 * * Or * * Compile: ocamlc -o makeMultTable.exe makeMultTable.ml * Execute: makeMultTable 230 5100 * * Date: 2013. 2. 2). * Author: pkim __AT__ scripts.pe.kr *) open ..