[JAVA] n이하의 소수를 구하는 알고리즘

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

소수
소수는 자신과 1 이외의 정수로 나누어떨어지지 않는 정수이다.
예를 들어 소수 13은 2, 3, ..., 12 가운데 어떤 정수로도 나누어 떨어지지 않는다
그러므로 어떤 정수 n에 대하여 아래의 조건을 만족하면 소수임을 알 수 있다.
"소수 n은 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않는다."

만약 나누어 떨어지는 정수가 하나 이상 존재하면 그 수는 합성수이다.

 

n 이하의 소수를 나열하는 알고리즘 (시간복잡도 높음, 공간복잡도 낮음)

static void PrimeNumber(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        for(int j = 2; j <= i; ++j)
        {
            if(i == j) System.out.println(i);
            if(i % j == 0) break;
        }
    }
}

설명
바깥쪽 루프는 2부터 n까지 반복을 하고, 안쪽 루프는 2부터 i까지 반복한다.
i와 j가 같다면(안쪽 루프와 바깥쪽 루프를 모두 돌았다면) 소수인 것이므로 출력한다.
i를 j로 나눈 나머지가 0이라면 소수가 아니므로 루프(안쪽)를 탈출한다.

 

실행 예제

public class Main{
	static void PrimeNumber(int n)
	{
		for(int i = 2; i <= n; ++i)
		{
			for(int j = 2; j <= i; ++j)
			{
				if(i == j) System.out.println(i);
				if(i % j == 0) break;
			}
		}
	}
	public static void main(String[] args) {
		PrimeNumber(55);
	}
}
/*
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
*/

 

 

알고리즘 개선1 (시간복잡도 중간, 공간복잡도 높음)

처음 제시한 알고리즘은 불필요한 연산을 하고 있다.

어떤 수가 2 또는 3으로 나누어 떨어지지 않으면 2X2인 4 또는 2X3인 6으로도 나누어 떨어지지 않는다.

따라서 어떤 수가 소수인지 여부는 아래의 조건을 만족하는지 조사하면 된다.

"소수 n은 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다."

예를 들어 7이 소수인지는 7보다 작은 소수(2, 3, 5)로 나눗셈을 하면 충분하다. 이렇게 하면 성능을 향상할 수 있다.

static void PrimeNumber(int n)
{
    int []arr = new int[n]; //소수를 저장하기 위한 배열을 동적할당
    int count = 0; //소수의 개수를 저장
    arr[count++] = 2; //arr[0]에 2를 저장하고 count를 +1 증가시킴
    for(int i = 3; i <= n; i += 2) //짝수는 검사하지 않음
    {
        int j;
        for(j = 1; j < count; ++j) if(i % arr[j] == 0) break;
        if(j == count) arr[count++] = i;
    }
    for(int i = 0; i < count; ++i) System.out.println(arr[i]);
}

설명
2는 소수이므로 arr[0]에는 2를 넣고
바깥 루프는 3부터 n까지 반복을 진행하고, 안쪽 루프는 1부터 count -1까지 반복한다.
안쪽 루프에서 i를 arr[j]로 나누고 나머지가 0이면 루프를 탈출한다.
안쪽 루프를 다 돌고 j와 count가 같다면 arr[count]에 i를 대입한다.

위 알고리즘은 시간복잡도는 감소하지만, 공간복잡도는 증가한다. (연산횟수는 감소하지만, 메모리 사용량은 증가한다)

 

실행예제

public class Main{
	static void PrimeNumber(int n)
	{
		int []arr = new int[n]; //소수를 저장하기 위한 배열을 동적할당
		int count = 0; //소수의 개수를 저장
		arr[count++] = 2; //arr[0]에 2를 저장하고 count를 +1 증가시킴
		for(int i = 3; i <= n; i += 2) //짝수는 검사하지 않음
		{
			int j;
			for(j = 1; j < count; ++j) if(i % arr[j] == 0) break;
			if(j == count) arr[count++] = i;
		}
		for(int i = 0; i < count; ++i) System.out.println(arr[i]);
	}
	public static void main(String[] args) {
		PrimeNumber(55);
	}
}
/*
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
*/

 

알고리즘 개선2 (시간복잡도 낮음, 공간복잡도 높음)

100의 약수를 구하는 과정은 아래와 같다.

• 2 X 50
• 4 X 25
• 5 X 20
• 10 X 10
• 20 X 5
• 25 X 4
• 50 X 2

10 X 10을 기준으로 위아래는 똑같다.

기준을 잡고 기준을 포함해서 위나 아래만 하나를 골라서 소수로 나눗셈을 시도하고, 그 과정에서 한 번도 나누어 떨어지지 않으면 소수라고 판단한다는 것이다.

(예를 들어 100이 5로 나누어떨어지지 않는다면 20으로도 나눠어 떨어지지 않는다.)

따라서 어떤 수가 소수인지 여부는 아래의 조건을 만족하는지 조사하면 된다.

"소수 n은 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다."

static void PrimeNumber(int k)
{
    int count = 0;
    int[] arr = new int[k];

    arr[count++] = 2;
    arr[count++] = 3;

    for (int i = 5 ; i <= k; i += 2) {
        boolean flag = false;
        for (int j = 1; arr[j] * arr[j] <= i; j++) {
            if (i % arr[j] == 0) flag = true; break;
        }
        if (!flag) arr[count++] = i;
    }
    for (int i = 0; i < count; i++)System.out.println(arr[i]);
}

 

실행예제

public class Main{
	static void PrimeNumber(int k)
	{
		int count = 0;
		int[] arr = new int[k];

		arr[count++] = 2;
		arr[count++] = 3;

		for (int i = 5 ; i <= k; i += 2) {
			boolean flag = false;
			for (int j = 1; arr[j] * arr[j] <= i; j++) {
				if (i % arr[j] == 0) flag = true; break;
			}
			if (!flag) arr[count++] = i;
		}
		for (int i = 0; i < count; i++)System.out.println(arr[i]);
	}
	public static void main(String[] args) {
		PrimeNumber(1000);
	}
}
/*
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
*/

 

첫번째 알고리즘의 연산 횟수는 78022

두 번째 알고리즘의 연산 횟수는 14622

세 번째 알고리즘의 연산 횟수는 3774