백준 1747번:소수&팰린드롬

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

정수 n을 입력 받고
n보다 크거나 같은 수 중 소수이면서, 펠린드롬인 수 중 가장 작은 수를 구하면 된다.

한자리 수는 펠린드롬으로 친다.

펠린드롬을 구하거나, 소수를 구하는 알고리즘은 크게 어렵지 않다.
그러나 n이 1일 때와 같이 특수한 상황의 예외처리를 잘해야한다.

앞서 소수 구하는 알고리즘과 펠린드롬 구하는 알고리즘을 연습해두면 30분이면 풀 수 있는 문제다. 왜 실버1인가 싶은 문제였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class n1747 {
	public static boolean pelindrome(int n) {
		char[] num = (String.valueOf(n)).toCharArray();
		for(int i=0;i<num.length/2;i++) {
			if(num[i] != num[num.length-1-i]) {
				return false;
			}
		}
		return true;
	}
	public static boolean decimal(int n) {
		if((n!=2 && n%2 == 0) || n==1) { 
			return false;
		} //짝수일 경우, 1일 경우 전부 false
		for(int i =2;i<= n/2; i++) {
			if(n%i==0) {
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n= Integer.parseInt(br.readLine());
		
		while(!(pelindrome(n) ==true && decimal(n) == true) ) {
			n++;
		}
		bw.write(String.valueOf(n));
		bw.flush();
		bw.close();
		br.close();
	}
}

백준 1990번: 소수인팰린드롬

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

위에 문제와 비슷하다.
정해진 범위내에 소수이면서 펠린드롬인 수를 모두 출력하면 된다.

다만 이 문제에선 소수를 구할 때 에라토스테네스의 체를 사용하지 않으면 시간초과가 난다.
배열을 최대 크기만큼 만든 뒤 에라스토네스의 체로 소수만 걸러낸 뒤 펠린드롬인지 아닌지 비교해야한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class n1990 {
	static final int MAX = 100000001;
	static boolean[] isPrime = new boolean[MAX];

	public static boolean pelindrome(int n) {
		char[] num = (String.valueOf(n)).toCharArray();
		
		for (int i = 0; i < num.length / 2; i++) {
			if (num[i] != num[num.length - 1 - i]) {
				return false;
			}
		}
		
		return true;
	}

	public static void Erastos() {
		isPrime[0] = isPrime[1] = true;
		for (int i = 2; i * i < MAX; i++) {
			if (!isPrime[i]) {
				for (int j = i * i; j < MAX; j += i) {
					isPrime[j] = true;
				}
			}
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		Erastos();

		while (!(n > k)) {
			if (isPrime[n] == false) {
				if (pelindrome(n) == true) {
					bw.write(String.valueOf(n) + "\n");
				}
			}
			n++;
		}
		
		bw.write("-1");
		bw.flush();
		bw.close();
		br.close();
	}
}

에라토스테네스의 체 알고리즘이 이해가 잘 되지 않는다.

에라토스테네스의 체 연습 코드이다.

public class Eratos_practice {

	static final int MAX= 501;
	static boolean[] arr= new boolean[MAX];
    
	public static void Eratos() {
		arr[0]=arr[1]=true;
		
		for(int i=2;i*i<MAX;i++) {
			if(!arr[i]) {
				for(int j=i*i;j<MAX;j+=i) {
					System.out.println("현재 i는 "+i+", 현재 j는 "+j);
					arr[j]=true;
				}
			}
		}
		
	}
	public static void main(String[] args) {
		Eratos();
	}
}

2의 배수가 모두 지워지고 3의 배수가 지워지기 시작한다.

그 후 소수의 배수인 것들이 지워지기 시작한다.

20, 21, 22..이런 것들은 이미 지워져있다.
23 * 23은 501을 넘으니 23의 배수는 지워지지 않는다.

백준 6219번: 소수의 자격

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

연습 문제로 소수 문제를 한개 더 풀었다.
범위 내의 소수를 구한뒤 그 소수가 정수 D를 포함하고 있는지 확인하는 문제이다.
확인은 String 형식으로 변환 후 contatins 메소드를 이용했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class n6219 {
	static final int MAX= 4000001;
	static boolean[] arr= new boolean[MAX];
	public static void Eratos() {
		arr[0]=arr[1]=true;
		
		for(int i=2;i*i<MAX;i++) {
			if(!arr[i]) {
				for(int j=i*i;j<MAX;j+=i) {

					arr[j]=true;
				}
			}
		}
		
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		int A= Integer.parseInt(st.nextToken());
		int B= Integer.parseInt(st.nextToken());
		int D= Integer.parseInt(st.nextToken());
		int count =0;
		Eratos();
		
		while(A<B) {
			if(arr[A]==false && String.valueOf(A).contains(String.valueOf(D))) {
				count++;
			}
			A++;
		}
		
		bw.write(String.valueOf(count));
		bw.flush();
		bw.close();
		br.close();
	}
}