Thursday, October 05, 2006

자바/Java] 소수 찾기/만들기 (素數): Prime Number Generator

"1"과 "자기 자신"으로만 나누어지는 자연수가 소수(Prime Number)입니다. 사실상 어떤 수로도 나누어지지 않는 수입니다.

2, 3, 5, 7, 11, 13 ...

이렇게 2부터 시작하여 무한히 계속 나타납니다. 소수 중에서는 "2"가 유일한 짝수이고, 다른 소수는 모두 홀수입니다. 따라서 소수를 찾을 때는 우선 2를 적어 놓고, 그 다음부터는 홀수 속에서만 찾으면 됩니다.

아래의 소스는, 소수 찾기 알고리즘 중에서 중간 정도의 속도를 가지고 있습니다.

소수라는 것은 "찾는" 것이고, "만드는" 것이 아니지만 편의상 만들기라고 부릅니다.

소수(Prime Number) 찾기/만들기 예제

파일명: Foo.java

public class Foo {
public static void main(String argv[]) {

System.out.println("2\r\n3");

for (int i = 5; i < 0xFFFFFF; i += 2)
if (isPrime(i)) System.out.println(i);

}

private static boolean isPrime(int number) {
if (number % 3 == 0) return false;

int y = 2;
int x = (int) Math.sqrt(number);

for (int i = 5; i <= x; i += y, y = 6 - y)
if (number % i == 0) return false;

return true;
}
}

실행 결과: