소수는 자신과 1 이외의 어떤 정수로도 나누어 떨어지지 않는 정수이다.
(ex : 정수 13의 소수는 1과 13, 단 2개)
1,000이하의 소수를 나열하는 프로그램 (Ver.1)
중요하다고 생각하는 포인트
int i; 선언은 for문 하단에 int i가 for문 밖에서 사용되기 때문에 따로 선언되었다.
이중for문이 이 코드의 핵심인 것 같다.
for (int n = 2; n <= 1000; n++) {
int i;
for (i = 2; i < n; i++) {
counter++;
if (n % i == 0) // 나누어떨어지면 소수가 아님
break; // 반복은 더 이상 불필요- n이 소수인 경우 : 안쪽 for문의 i값이 n값과 같음 (for문이 중단없이 끝까지 실행됨)
(나누어 떨어지는 값이 없다는 것을 의미)
- n이 합성수인 경우 : 안쪽 for문의 i값이 b값보다 작음(for문이 도중에 중단됨)
전체코드
package DataStructureBasic;
// 1,000 이하의 소수를 나열하는 프로그램(Ver.1）
class PrimeNumber1 {
public static void main(String[] args) {
int counter = 0; // 나눗셈 횟수
for (int n = 2; n <= 1000; n++) {
int i;
for (i = 2; i < n; i++) {
counter++;
if (n % i == 0) // 나누어떨어지면 소수가 아님
break; // 반복은 더 이상 불필요
}
if (n == i) // 마지막까지 나누어떨어지지 않음
System.out.println(n);
}
System.out.println("나눗셈을 수행한 횟수 : " + counter);
}
}
이런식으로 출력이 된다.
하지만 Ver.1의 경우 불필요한 나눗셈을 많이 한다.
예를 들어 7이 약수인지 확인하기 위해 2부터 2..3..4..5..로 나뉘어지는지 모두 계산한다.
소수인지 확인하기 위해서는 7보다 작은 소수 2,3,5로 나눗셈을 하면 충분하다.
♬
1,000이하의 소수를 나열하는 프로그램 (Ver.2)
위에 있는 Ver.1의 알고리즘 개선버전!
중요하다고 생각하는 포인트
prime[ptr++] = 2; // 2는 소수임
for (int n = 3; n <= 1000; n += 2) { // 조사 대상은 홀수만
int i;
for (i = 1; i < ptr; i++) { // 이미 찾은 소수로 나누어 봄
counter++;
if (n % prime[i] == 0) // 나누어떨어지면 소수가 아님
break; // 더 이상의 반복은 불필요
}
if (ptr == i) // 마지막까지 나누어떨어지지 않음
prime[ptr++] = n; // 소수로 배열에 저장Ver.1과 마찬가지로 이중for문을 통해 구한다.
바깥쪽 for문은 n값을 2씩 증가시켜 3,5,7,9...,999 홀수값만을 생성한다.
4이상의 짝수는 2로 나누어떨어지므로 소수가 아니기 때문이다.
(출처:Do it! 알고리즘 입문 - 자바편)
전체코드
package DataStructureBasic;
// 1,000이하의 소수를 나열하는 프로그램(Ver.2）
class PrimeNumber2 {
public static void main(String[] args) {
int counter = 0; // 나눗셈 횟수
int ptr = 0; // 찾은 소수의 개수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2; // 2는 소수임
for (int n = 3; n <= 1000; n += 2) { // 홀수만, 조사대상 +2씩 증가
int i;
for (i = 1; i < ptr; i++) { // 이미 찾은 소수로 나누어 봄
counter++;
if (n % prime[i] == 0) // 나누어떨어지면 소수가 아님
break; // 더 이상의 반복은 불필요
}
if (ptr == i) // 마지막까지 나누어떨어지지 않음
prime[ptr++] = n; // 소수로 배열에 저장
}
for (int i = 0; i < ptr; i++) // 찾은 ptr개의 소수를 출력
System.out.println(prime[i]);
System.out.println("나눗셈을 수행한 횟수 : " + counter);
}
}Ver.1과 Ver.2의 답은 같지만 알고리즘은 다르다.
빠른 알고리즘은 메모리를 많이 사용하는 경향이 있다.
♬
1,000이하의 소수를 나열하는 프로그램 (Ver.3)
위에 있는 Ver.2의 알고리즘 개선버전!
중요하다고 생각하는 포인트
//안쪽 for문에 있는 prime[i]가 n의 제곱근 이하인지 판단하는 부분
for (int i = 1; prime[i] * prime[i] <= n; i++) n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않음 = 소수이다.
(출처:Do it! 알고리즘 입문 - 자바편)
예를 들어 4X25와 25X4는 대칭을 이루고 똑같이 넓이 100을 가진다.
즉, 이 말은 대칭의 중심인 정사각형 10X10 뒤로는 앞에서 이미 나눗셈을 한 것과
같은 결과가 나타나므로 중복하여 나눗셈할 필요가 없는 것이다.
대칭의 기준이 되는 정사각형 10X10의 한 변의 길이(10)까지만 소수로 나눗셈을 하고,
그 과정에서 나누어지지 않으면 소수로 판단할 수 있다는 것이다.
이렇게 불필요한 계산을 줄이는 것이 Ver.3의 핵심 알고리즘이다.
전체코드
package DataStructureBasic;
// 1,000이하의 소수를 나열하는 프로그램 (Ver.3）
class PrimeNumber3 {
public static void main(String[] args) {
int counter = 0; // 곱셈과 나눗셈의 횟수
int ptr = 0; // 찾은 소수의 개수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2; // 2는 소수입니다
prime[ptr++] = 3; // 3은 소수입니다
for (int n = 5 ; n <= 1000; n += 2) { // 조사 대상은 홀수만
boolean flag = false;
for (int i = 1; prime[i] * prime[i] <= n; i++) {
counter += 2;
if (n % prime[i] == 0) { // 나누어떨어지면 소수가 아님
flag = true;
break; // 더 이상 반복은 불필요
}
}
if (!flag) { // 마지막까지 나누어떨어지지 않음
prime[ptr++] = n; // 소수로 배열에 저장
counter++;
}
}
for (int i = 0; i < ptr; i++) // 찾은 ptr개의 소수를 출력
System.out.println(prime[i]);
System.out.println("곱셈과 나눗셈을 수행한 횟수: " + counter);
}
}