(소수와 합성수)
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) 보다 작거나 같은 모든 정수로 나누어 본다.
이 경우 언제나 나누어 떨어지지 않으면 n은 소수이고, 그렇지 않으면 n은 합성수이다.
우선 다음의 Groovy 소스 코드는 명령행 인자로 전달 받은 양의 정수 n을
2 및 3, 5, 7, ... , sqrt(n) 이하의 홀수들로 나누어 보아 n이 합성수인지 아닌지
확인하는 애플리케이션 소스이다. 확인하는데 걸린 경과 시간도 알려준다.
/*
* Filename: divideEach.groovy
*
* Purpose: Determine whether the given integer is a prime or not.
*
* Execute: groovy divideEach.groovy [integer]
*
* Date: 2009/03/23
* Author: PH Kim [ pkim ((AT)) scripts.pe.kr ]
*/
/*
Execution Examples (with Groovy 1.6.0):
Prompt> groovy divideEach.groovy 1234567812343
1234567812343 = 1 * 1234567812343
1234567812343 is a prime
Elapsed time: 4.953 sec
Prompt> groovy divideEach.groovy 9999994200000841
9999994200000841 = 99999971 * 99999971
9999994200000841 is a not prime
Elapsed time: 468.688 sec
Prompt> groovy divideEach.groovy 18446744073709551617
18446744073709551617 = 274177 * 67280421310721
18446744073709551617 is a not prime
Elapsed time: 1.594 sec
Prompt> groovy divideEach.groovy 10023859281455311421
10023859281455311421 = 1308520867 * 7660450463
10023859281455311421 is a not prime
Elapsed time: 3521.562000 sec
*/
BigInteger n = 10006099720301
if (args.length > 0) {
n = new BigInteger(args[0])
}
BigInteger z = n / 2G // z = n / 2
if (n == 2G*z) {
print "${n} = 2 * ${z}\n"
}
def time1 = new GregorianCalendar().getTime().getTime()
BigInteger d = 1
BigInteger k = 3
while (k*k <= n) {
z = n / k // z = n / k
if (n == k*z) {
d = k
break
}
k = k + 2G
}
def time2 = new GregorianCalendar().getTime().getTime()
print "$n = $d * ${n/d}\n"
if (d == 1)
print "$n is a prime\n"
else
print "$n is a not prime\n"
이제 다음은 정수의 인수분해 능력이 뛰어난 Pollard의 rho 방법(일명 거북이와 토끼 알고리즘, tortoise-hair algorithm)을 구현한 Groovy 소스 코드이다. 이 알고리즘은 소수에 대해서는 시간이 많이 걸리지만, 합성수에 대해서는 시간이 매우 적게 걸린다는 것이 특징이다.
Prompt> groovy pollardRho.groovy 1234567812343
Try first the Pollard rho algorithm with c = 2
d = 1234567812343, count = 466951
Try second the Pollard rho algorithm with c = 3
d = 1, count = 1111112
Try third the Pollard rho algorithm with c = 1
d = 1234567812343, count = 799441
1234567812343 = 1234567812343 * 1
Elapsed time: 33.937 sec
Prompt> groovy pollardRho.groovy 9999994200000841
Try first the Pollard rho algorithm with c = 2
d = 99999971, count = 3593
9999994200000841 = 99999971 * 99999971
Elapsed time: 0.156 sec
Prompt> groovy pollardRho.groovy 18446744073709551617
Try first the Pollard rho algorithm with c = 2
d = 274177, count = 1028
18446744073709551617 = 274177 * 67280421310721
Elapsed time: 0.11 sec
Prompt> groovy pollardRho.groovy 10023859281455311421
Try first the Pollard rho algorithm with c = 2
d = 1308520867, count = 20350
10023859281455311421 = 1308520867 * 7660450463
Elapsed time: 0.579 sec
*/
BigInteger f(BigInteger x, BigInteger c, BigInteger n) {
return (x*x + c) % n
}
BigInteger gcd(BigInteger x, BigInteger y) {
BigInteger a, b, t
a = x.abs()
b = y.abs()
if (b == 0G) {
return a
}
while (b != 0G) {
t = a % b
a = b
b = t
}
return a
}
BigInteger pollardRho(BigInteger n) {
BigInteger c = 2G
BigInteger x = 1G
BigInteger y = 1G
BigInteger d = 1G
BigInteger savedX = x
BigInteger count = 0
println("Try first the Pollard rho algorithm with c = $c")
while (d == 1G && count*count <= n) {
x = f(x, c, n)
if (x == savedX) {
println("It is cyclic. x = $x")
break
}
y = g(y, c, n)
d = gcd((x - y).abs(), n)
count = count + 1
// if (count % 5000 == 0) {
// println(" count = $count")
// }
}
println("d = $d, count = $count")
if (d > 1 && d < n) {
return d
}
c = 3
x = 1
y = 1
d = 1
savedX = x
count = 0
println("Try second the Pollard rho algorithm with c = $c")
while (d == 1 && count*count <= n) {
x = f(x, c, n)
if (x == savedX) {
println("It is cyclic. x = $x")
break
}
y = g(y, c, n)
d = gcd(Math.abs(x - y), n)
count = count + 1
// if (count % 5000 == 0) {
// println(" count = $count")
// }
}
println("d = $d, count = $count")
if (d > 1 && d < n) {
return d
}
c = 1
x = 1
y = 1
d = 1
savedX = x
count = 0
println("Try third the Pollard rho algorithm with c = $c")
while (d == 1 && count*count <= n) {
x = f(x, c, n)
if (x == savedX) {
println("It is cyclic. x = $x")
break
}
y = g(y, c, n)
d = gcd(Math.abs(x - y), n)
count = count + 1
// if (count % 5000 == 0) {
// println(" count = $count")
// }
}
println("d = $d, count = $count")
return d
}
BigInteger n, k, z
n = 9991
if (args.length > 0) {
n = new BigInteger(args[0])
}
def time1 = new GregorianCalendar().getTime().getTime()
k = pollardRho(n)
z = n/k
// if (n == k*z) {
println("$n = $k * $z")
// }
def printUsing() {
println "Using: groovy makeMultTable.groovy [number1] [number2]"
println "Print a multiplication table for the given two integers."
}
Groovy 언어는 Java 언어와 달리 한 개의 소스 파일 내에 public 이든 아니든 여러 개의 클래스가 존재해도 된다. 또 클래스명과 다른 파일명으로 저장해도 된다. Groovy 언어도 Java, C 언어 처럼 대소문자 구별을 엄격히 하지만 public 클래스와 대소문자만 듵린 파일명으로 저장해도 아무 상관 없다.
다음은 두 개의 클래스로 구성되어 있다. Parent는 부모 클래스이고 Child는 Parent에서 상속 받은 자식 클래스이다.
// Filename: testSubclassing.groovy public class Parent { private String name public Parent(String name) { // 생성자 this.name = name } public void sayName() { println("I am Parent, " + name) } }
public class Child extends Parent { private String name public Child(String name) { // 생성자 super(name) // 클래스 상속시 부모 클래스 생성자 호출 this.name = name } public void sayName() { println("I am a child, named as " + name) } }
def obj = new Child("Dooly") // 클래스 생성 obj.sayName()
실행> groovy testSubclassing.groovy I am a child, named as Dooly
을 출력하는 Groovy 소스 코드를 작성해 보자. 이런 소스 코드의 작성은 학원이나 학교에서 프로그래밍 입문자에게 과제로 많이 주어지는 것 중의 하나이다. 코끼리를 보거나 만진 사람들이 저마다 그 생김새를 말할 때 제각기 다르게 표현할 수 있듯이 이런 소스 코드의 작성도 알고 보면 얼마든지 많은 방법이 있을 것이다. 여기서는 쉬운 코드 부터 작성해 보고 차츰차츰 소스를 바꾸어 가면서 Groovy 프로그래밍의 기초부분을 터득해 보기로 한다.
모든 소스 코드에서는 삼각형 출력 부분 담당 함수 printTriange()를 별도로 구현하였다.
우선 첫번 째 예제는 Groovy의 컨솔 출력 함수 println()의 사용법 만 알면 누구나 코딩할 수 있는 매우 단순한 소스 코드이다.
삼각형 출력 예제 1 /* * Filename: printTriangle1.groovy * Print a triangle on console. * * Execute: groovy printTriangle1.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
위의 소스 코드는 아무 알고리즘도 없는 너무 단순한 코드이다. 이런 코드를 작성했다간 출력 모양이나 크기를 변경해야 하는 상황을 맞이하면 워드프로세서로 문서 만드는 것 이상으로 많은 수작업을 하거나 아니면 포기하는 지경에 이를 수도 있다. 그래서 다음 처럼 좀 더 나은 소스 코드를 작성하였다.
삼각형 출력 예제 2 /* * Filename: printTriangle2.groovy * Print a triangle on console. * * Execute: groovy printTriangle2.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { for (i in 0..<8) { for (k in 0..<8-i) { print(" ") } for (k in 0..<2*i+1) { if (k == 0 || k == 2*i) print("*") else print(" ") } for (k in 0..<8-i) { print(" ") } println() }
for (i in 0..<17) { print("*") } println() }
printTriange()
위의 소스 코드는 Groovy의 컨솔 출력 함수 println()와 print() 그리고 for 반복 구문을 적절히 사용하여 구현되었다. 숫자 몇 곳만 수정하면 출력되는 삼각형의 크기를 바꿀 수 있다. 한 줄에 출력될 문자를 구성하는 알고리즘은 위의 예제와 근본적으로 같지만 print()를 사용하지 않고, 그대신 char[] 타입의 배열을 만들어 한 즐씩 출력하는 소스 코드를 다음 예제와 같이 작성해 보았다. 또 빈칸 17개의 문자로 구성된 스트링을 생성하기 위한 구문
def whites = " "*17
도 음미해볼 만하다. (string*number 또는 list*number의 구문은 Python, Ruby 언어에서도 지원된다.)
삼각형 출력 예제 3 /* * Filename: printTriangle3.groovy * Print a triangle on console. * * Execute: groovy printTriangle3.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def line = " "*17 def line2 = " "*17 as char[]
for (int i in 0..<8) { ine2 = " "*17 as char[] line2[8-i] = '*' line2[8+i] = '*' println(new String(line2)) }
line2 = " "*17 as char[] for (i in 0..<17) { line2[i] = '*' } println(new String(line2)) }
printTriange()
별(*) 문자를 이용하여 삼각형을 출력하는 일은 빈칸 문자와 별 문자를 적당한 좌표(위치)에 촐력하는 일이다. StringBuffer를 사용하더라도 한 줄의 출력을 빈칸 만으로로 구성된 string(소스 코드에서 변수 whites가 참조하는 string 값)을 기본으로 하고, 이 string에 한 두 개의 빈칸을 바꾸어 출력하는 기법으로 작성한 것이 다음 소스 코드이다. 단, 마지막 줄에 츨력될 string은 stars라는 별도의 변수로 처리하였다.
삼각형 출력 예제 4 /* * Filename: printTriangle4.groovy * Print a triangle on console. * * Execute: groovy printTriangle4.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def whites = " "*17 def stars = "*"*17 def line2 = new StringBuffer(whites) line2 = line2.replace(8, 9, "*") println(line2) for (int i in 1..<8) { line2 = new StringBuffer(whites) line2 = line2.replace(8-i, 8+i, stars.substring(8-i, 8+i)) line2 = line2.replace(8-i+1, 8+i-1, whites.substring(8-i, 8+i-1)) println(line2) } println(stars) }
printTriange()
빈칸 문자를 별(*) 문자로 바꾸기 위해, 위의 소스 코드에서는 StringBuffer.replace() 메소드를 이용하였지만, 다음 소스 코드에서는 StringBuffer.setCharAt() 메소드를 이용하였다.
삼각형 출력 예제 5 /* * Filename: printTriangle5.groovy * Print a triangle on console. * * Execute: groovy printTriangle5.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def whites = " "*17 def stars = "*"*17 def line = new StringBuffer(whites) def start = 8 line = line.replace(start, start, "*") println(line) for (int i in 1..<8) { line = new StringBuffer(whites) line.setCharAt(start - i, stars.charAt(start - i)) line.setCharAt(start + i, stars.charAt(start + i)) println(line) } println(stars) }
printTriange()
출력되는 삼각형이 좌우 대칭이라는 사실에 착안하여, 다음 소스 코드에서는 각 줄을 처음 8자, 중앙 한 문자, 끝 8자(처음 8자의 역순)로 string을 만들어 출력하였다.
삼각형 출력 예제 6 /* * Filename: printTriangle6.groovy * Print a triangle on console. * * Execute: groovy printTriangle6.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
for (int i in 1..<8) { line = new StringBuffer(whites) line.setCharAt(start - i, stars.charAt(start - i)) print(line) print(" ") line.reverse() println(line) }
line = new StringBuffer(stars) line.append('*') line.append(stars) println(line) }
printTriange()
다음 소스 코드는 한 줄에 출력될 문자열의 데이터를 17비트 이진법 수로 구성하고, 이 이진법수의 비트가 0인 곳에는 빈칸을, 1인 곳에는 별(*)을 출력하는 기법으로 작성되었다.
삼각형 출력 예제 7 /* * Filename: printTriangle7.groovy * Print a triangle on console. * * Execute: groovy printTriangle7.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def start = 0x100 def total = 0 def val = start def data = ""
for (k in 0..<8) { val = (start << k) | (start >> k) data = Integer.toString(val, 2) for (i in 0..<17 - data.length()) { print(' ') } for (i in 0..<data.length()) { if (data[i] == '0') print(' ') else print('*') } println() total += val }
val = (start << 8) | (start >> 8) total += val data = Integer.toString(total, 2) for (i in 0..<17 - data.length()) { print(' ') } for (i in 0..<data.length()) { if (data[i] == '0') print(' ') else print('*') } println() }
printTriange()
기본적인 원리는 위의 소스 코드와 같지만 이진법수의 한 비트 마다 한 문자씩 츨력하는 대신에 출력된 한 줄의 string을 완성하여 이를 println() 으로 출력하는 기법으로 재작성한 것이 다음의 소스 코드이다. String.replaceAll() 메소드를 이용하여 모든 0을 빈칸으로, 모든 1을 별(*) 문자로 바꾸었으며, 별(*) 문자만으로 이루어진 마지막 줄 출력을 위해 변수 total을 준비하였다. for 반복 구문의 블럭 내에서 구문
total |= val
이 하는 일이 무엇인지 이해할 수 있으면 좋겠다.
삼각형 출력 예제 8 /* * Filename: printTriangle8.groovy * Print a triangle on console. * * Execute: groovy printTriangle8.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def zeros = "00000000" def start = 0x100 def total = 0 def val = start def line = "" def data = ""
for (k in 0..<8) { val = (start << k) | (start >> k) data = Integer.toString(val, 2) line = zeros[0..<17-data.length()] + data line = line.replaceAll("0", " ") line = line.replaceAll("1", "*") println(line) total |= val }
val = (start << 8) | (start >> 8) total |= val line = Integer.toString(total, 2) line = line.replaceAll("0", " ") line = line.replaceAll("1", "*") println(line) }
printTriange()
소스 코드가 처음 것 보다 매우 복잡해졌지만, Groovy의 리스트를 이용해서 구현해 보았다. Groovy 언어 외에 Python, Ruby 언어 같은 스크립팅 언어에서도 리스트와 맵은 매우 중요하게 취급되며, 구문에서도 이를 위한 문법을 제공하고 있다. 별(*) 문자만으로 이루어진 마지막 줄 출력을 위해 리스트 타입의 변수 last를 준비하였다. 또 리스트에 속한 모든 item을 출력하는 부분
data.each { print it } println
은 Groovy 언어에서 많이 사용되는 클로저(closure)를 이용한 구문이다. 이 두 줄은 리스트의 join 메소드를 이용하여
println( data.join() )
로 해도 같은 출력을 얻는다.
삼각형 출력 예제 9 /* * Filename: printTriangle9.groovy * Print a triangle on console. * * Execute: groovy printTriangle9.groovy * * Date: 2008/04/01 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def start = 8 def data = [" "]*17 def last = [" "]*17
삼각형 출력 예제 10 /* * Filename: printTriangle10.groovy * Print a triangle on console. * * Execute: groovy printTriangle10.groovy * * Date: 2008/04/03 * Author: PH Kim [ pkim (AT) scripts.pe.kr ] */
def printTriange() { def a for (y in 0..8) { for (x in 0..16) { if ((x + y - 8 == 0) || (y - x + 8 == 0) || (y - 8 == 0)) a = '*' else a = ' ' print a } println() } }
ASCII(애스키)란 American Standard Cpde for Information Interchange의 줄임글로서, 영문자에 기초한 문자 인코딩이다. 이 문자 인코딩에는 C0 제어문자(C0 control character)도 포함되어 있다. ( 참고: ASCII - Wikipedia, the free encyclopedia )
다음은 7bit ASCII 코드표를 만들어 보여주는 Groovy 소스 코드이다. 소스 코드 중에 진법변환에 필요한 함수