[java]백준 1747번: 소수&팰린드롬, prime number 소수, 아리토스테네스의 체 원리, 제곱 Math.pow(a,b)

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

소수prime nuber
자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수
1과 자기 자신 외에 약수가 존재하지 않는 수

 

소수 구하기의 핵심 이론

에라토스테네스의 체 원리
① 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
② 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움. 이때 처음으로 선택된 숫자는 지우지 않음
③ 배열의 끝까지 ②를 반복한 후 배열에서 남아 있는 모든 수를 출력

-> 에라토스테네스의 체를 사용할 때 시간 복잡도는?
일반적으로 에타토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있습니다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))입니다. 그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문입니다. 이러한 이유  때문에 에라토스테네스의 체 기법은 현재에도 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용되고 있습니다.

 

---

 

코드

package javaCodingTest;

import java.util.Scanner;

public class j1747 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int result = 0;
		int[] prime = new int[1003002];
		for (int i = 2; i <= 1003001; i++) {
			prime[i] = i;
		}

		for (int i = 2; i <= 1003001; i++) {
			if (prime[i] == 0) {
				continue;
			}

			if (i >= N && pal(i) == true) {
				result = i;
				break;
			}

			for (int j = i + i; j <= 1003001; j = j + i) {
				prime[j] = 0;
			}

		}

		System.out.println(result);

	}

	static boolean pal(int num) {
		String temp = Integer.toString(num);
		char[] n = temp.toCharArray();
		for (int i = 0; i < n.length; i++) {
			if (n[i] != n[n.length - 1 - i]) {
				return false;
			}
		}
		return true;
	}
}

 

 

풀이

1. 소수는 에라토스테네스의 체 사용해서 구함 -> 에라토스테네스의 원리는 아래 게시물에서 확인 
2. 소수를 구할 때 범위는 B의 제곱근까지 → 소수의 제곱부터가 거의소수이기 때문에 (근데 귀찮아서 안했는데 돌아감!! 하지만 시간복잡도 때문에 제곱근까지 하는 거 중요)
3. 메소드 pal 사용하여 숫자가 팰린드롬 수 인지 확인! char[]로 바꿔 처음과 끝 비교

2022.10.03 - [알고리즘/백준] - [java]백준 1929번- 소수 구하기, prime number 소수, 제곱근 Math.sqrt(N), 아리토스테네스의 체 원리

[java]백준 1929번- 소수 구하기, prime number 소수, 제곱근 Math.sqrt(N), 아리토스테네스의 체 원리

 

Math.pow(a,b)
a의 b제곱

 

 

출처: 백준, Do it! 알고리즘 코딩테스트 자바 편