chapter 02에서는 배열과 클라스에 관한 내용이 들어있다.
하지만 기초적인 부분도 있어 포스팅에서는 배열 부분에 소수 구하는 여러 방식을 포스팅해보려 한다.소수 나열하기 1
// 1,000 이하의 소수를 나열(버전 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);
}
}위 코드는 1에서 1,000이하의 소수를 알아보는 과정이다.
우선 for문을 통해 2부터 1000까지의 수를 하나씩 나누어 본다.
만약 나누어 진다면 소수가 아니고, 나누어지지 않는다면 소수이다.
이때 중요한 점은 counter 횟수가 78022라는 점이다.
소수 나열하기 2
// 1,000 이하의 소수를 나열(버전 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) { // 조사 대상은 홀수만
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);
}
}이번에는 이전 소수 나열하기 1 코드를 개선한 코드이다.
이전 코드와 달리 for문을 홀수만을 사용하였다.
짝수일 경우 2로 나누어지기에 소수가 아니고, 이를 활용해 불필요한 과정을 생략한 것이다.
하지만 2는 소수이므로 prime[ptr++] = 2;로 prime[0]에 2를 넣었다.
다음은 for문에서 이미 찾은 소수들을 prime배열에 넣었고,
이를 활용해 prime에 들어있는 소수들이 현재 판별하는 값과 나눠지는지 확인한다.
만약 나누어떨어지지 않는 경우 이를 소수로 판별하고, prime 배열에 값을 추가한다.
->이러한 방식으로 할 경우 짝수는 판별하지 않고, 소수를 통해 소수를 판별하므로
counter 횟수가 14622로 이전보다 효율적인 코드가 탄생한다.
이때 횟수가 줄어든다고 해서 좋은 코드라고 단정 지을 수는 없다!!
대부분 빠른 알고리즘은 메모리를 많이 필요로 하는 경향이 있기 때문이다.
소수 나열하기 3
// 1,000 이하의 소수를 나열(버전 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);
}
}다음은 제곱근을 활용해 소수를 구하는 코드이다.
이는 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.라는 것을 활용한 알고리즘이다.
2중 for문에서 안쪽 for문을 확인하면 범위 설정을 prime[i]*prime[i]로 설정하였다.
이를 통해 prime[i]로 나누어 떨어지는지 확인 후 그렇지 않다면 소수로 판명하고 prime배열에 값을 저장해준다.
->이러한 방식으로 할 경우 짝수는 판별하지 않고, 소수의 제곱근으로 활용하고, 소수를 통해 소수를 판별하므로 counter 횟수가 3774로 이전보다 효율적인 코드가 탄생한다.
이렇듯 3가지 과정을 통해 소수를 구하는 알고리즘을 좀 더 빠르게 변환해보았다.
추가적으로 프로그래머스 문제를 통해 소수 찾기 문제를 풀어보자.
프로그래머스_소수 찾기
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예시
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
문제풀이 1 (제곱근 Math.sqrt(n))
public int solution(int n) {
int answer = 0;
for(int i=2; i<=n; i++){
boolean prime = true;
for(int j=2; j<=Math.sqrt(i); j++) {
if(i%j == 0) {
prime = false;
break;
}
}
if(prime==true) {
answer++;
}
return answer;
}위 문제는 제곱근을 사용하여 소수를 찾는 소수 나열하기 3과 동일하다.
하지만 Math()메소드를 통해 제곱근을 구하여 for문의 범위를 지정해주었다.
문제풀이 2 (에라토스테네스의 체)
public int solution(int n) {
int answer = 0;
// 소수 판별을 위한 boolean타입 배열 선언
boolean[] prime = new boolean [n+1];
for(int i=2; i<=n ; i++)
prime[i]=true;
// n의 제곱근 root
int root=(int)Math.sqrt(n);
//범위를 제곱근으로 설정
for(int i=2; i<=root; i++){
//i가 소수일 경우 그 배수를 false로 전환
if(prime[i]==true){
for(int j=i; i*j<=n; j++) {
prime[i*j]=false;
}
}
// prime배열의 인덱스값이 false일 경우 counting
for(int i =2; i<=n; i++) {
if(prime[i]==true)
answer++;
}
return answer;
}위 코드는 이전 제곱근을 사용하는 코드에 더불어 에라토스테네스의 체라는 소수 찾는 방법을 사용한 코드이다.
에라토스테네스의 체는 간단히 설명해 해당 소수의 배수를 지워나가는 방식으로 소수를 찾는 방식이다.
이를 위해 boolean타입의 배열 prime을 선언해주고 인덱스 값을 true로 변경하였다.
다음 제곱근 범위에 값들로 소수판별을 할 때 해당 수가 소수일 경우 그 배수들을 다 false로 전환한다.
