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

 

---

 

• 코드

실패 코드  : 입력 값을 +1 하면서 반복문을 돈다. 안쪽에선 소수, 팰린드롬을 체크하며 소수이면서 팰린드롬이면 출력                    후 반복문 종료. 결과는 시간 초과

 

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

public class Main{
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int input = Integer.parseInt(br.readLine())-1;

		while(true) {
			boolean decimalCheck= false;
			boolean palindromeCheck = true;
			
			input++;
			
			for(int i=2;i<input;i++) {
				if(input%i==0) 
					break;
				if(i==input-1) 
					decimalCheck = true;					
			}
			
			int j=(int)(Math.log10(input)+1)-1;
			for(int i=0;i<(int)(Math.log10(input)+1)/2;i++) {
				if(!Character.toString(Integer.toString(input).charAt(i)).equals(Character.toString(Integer.toString(input).charAt(j)))) {
					palindromeCheck = false;
					break;
				}
			}
			
			
			if(decimalCheck && palindromeCheck) {
				bw.write(input + "\n");
				break;
			}
			
		}
		
		bw.flush();
		bw.close();
	}
}

 

성공 코드 : 소수와 팰린드롬 체크하는 메소드를 만들어서 boolean으로 넘겨 받아서 체크하게 했다.

                소수 체크에서 Math.sqrt(number)를 통해 시간을 단축시켰다.

                결과는 맞았습니다!!

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int input = Integer.parseInt(br.readLine());
		if(input==1) {
			System.out.println(2);
			System.exit(0);
		}

		while(true) {
					
			if(isDecimal(input) && isPalindrome(input)) {
				System.out.println(input);
				break;
			}			
			input++;
		}
	}
	
	static boolean isDecimal(int number) {
		for(int i=2;i<=(int)Math.sqrt(number);i++) {
			if(number%i==0) 
				return false;
		}
		return true;
	}
	
	
	static boolean isPalindrome(int number) {
		char [] integerToCharArray = String.valueOf(number).toCharArray();
		int length = integerToCharArray.length-1;
		for(int i=0;i<=integerToCharArray.length/2;i++) {
			if(integerToCharArray[i] != integerToCharArray[length--]) 
				return false;
		}
		return true;
	}
}

 

 

다른 사람의 코드 : 시간이 빠르게 나오길래 가지고 왔다.

 

import java.io.*;
import java.util.*;

public class Main {
	private static boolean[] prime_num;
	public static void main(String[]args)throws IOException
	{
		prime_num= new boolean[1004001];
		prime_num[1]=true;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		if(n <=7) {
			Eratosthenes(10);
			for(int i = n; i<=10;i++) {
				if(!prime_num[i]) {
					System.out.println(i);
					break;
				}
			}
			}
		else {			
			   Eratosthenes(1004000);
				for(int i = n; i<=1004000;i++) {
					if(!prime_num[i]&&isPalindrome(i)==true) {
						System.out.println(i);
						break;
					}
				}
			}
		}
	
	private static void Eratosthenes(int n) {
		for(int i = 2; i*i <= n; i++) {
			if(prime_num[i]==false) {
				for(int k = i*i; k<=n; k+=i)
					prime_num[k]=true;
			}
		}
	} 
	private static boolean isPalindrome(int num) {
		String s = Integer.toString(num);
		if(s.length()%2==0) { 
			int i = 0;
			int j = s.length()-1;
			while(i<j) {
				if(s.charAt(i)!=s.charAt(j))
					return false;
				i++;
				j--;
			}
		}
		else { //홀수일 경우 
			int i =0 ;
			int j = s.length()-1;
			while(i!=j) {
				if(s.charAt(i)!=s.charAt(j)) 
					return false;
				i++;
				j--;
			}
		}
		return true;
	}
}