Thursday, October 05, 2006
자바/Java] 소수 찾기/만들기 (素數): Prime Number Generator
"1"과 "자기 자신"으로만 나누어지는 자연수가 소수(Prime Number)입니다. 사실상 어떤 수로도 나누어지지 않는 수입니다.
2, 3, 5, 7, 11, 13 ...
이렇게 2부터 시작하여 무한히 계속 나타납니다. 소수 중에서는 "2"가 유일한 짝수이고, 다른 소수는 모두 홀수입니다. 따라서 소수를 찾을 때는 우선 2를 적어 놓고, 그 다음부터는 홀수 속에서만 찾으면 됩니다.
아래의 소스는, 소수 찾기 알고리즘 중에서 중간 정도의 속도를 가지고 있습니다.
소수라는 것은 "찾는" 것이고, "만드는" 것이 아니지만 편의상 만들기라고 부릅니다.
파일명: Foo.java
실행 결과:
화면으로 그냥 출력하면 속도가 느리기에
java Foo > out.txt
이렇게 재지향(Redirection)하여, 결과를 파일로 직접 저장하면 빠릅니다.
이번에는 C로 만들어 보았습니다: ▶▶ C언어] 소수 계산: 소수(素數) 찾기/만들기: Prime Number Generator
☞ 자바(Java)
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;
}
}
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;
}
}
실행 결과:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
...이하 생략...
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
...이하 생략...
화면으로 그냥 출력하면 속도가 느리기에
java Foo > out.txt
이렇게 재지향(Redirection)하여, 결과를 파일로 직접 저장하면 빠릅니다.
이번에는 C로 만들어 보았습니다: ▶▶ C언어] 소수 계산: 소수(素數) 찾기/만들기: Prime Number Generator
☞ 자바(Java)
Post a Comment
<< Home