[c++] 백준 - 1747번: 소수&팰린드롬

1747번: 소수&팰린드롬 (acmicpc.net)

1747번: 소수&팰린드롬

 

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <cmath>
#include <string>
using namespace std;

bool isPrime(int n) {
	//1과 2는 밑의 반복문으로 판별이 안되기때문에 따로 조건문 정의
	if (n == 1) return 0;
	if (n == 2) return 1;
    //sqrt는 제곱근을 구하는 함수
	for (int i = 2; i < sqrt(n) + 1; i++) {
		if (n % i == 0) return 0;
	}
	return 1;
}

bool isPalindrome(int n) {
	//n을 string으로 만들어줌
	string n_str = to_string(n);
	int len = n_str.length();
	for (int i = 0; i < len/2; i++) {
		if (n_str[i] != n_str[len - i - 1]) {
			return 0;
		}
	}
	return 1;
}

int main(void){
	int n;
	cin >> n;
	while (1) {
		if ( isPalindrome(n) && isPrime(n) ) {
			cout << n;
			break;
		}
		else n++;
	}

	return 0;
}

 

처음 어떻게 풀까 생각할때 에라토스테네스의 체를 쓸까 생각하였지만 수의 범위를 어디까지 설정해야할지 감으로 정할수가 없어서 제곱근까지 i로 계속 나눠주는 방법을 사용하였다. 

 

하지만 최대 범위가 N (1 ≤ N ≤ 1,000,000)라고 주어져있기때문에 1000000이란 숫자를 이용하여 조건에 맞는 수를 일단 구하고(1003001) 그 범위까지 에라토스테네스의 체를 사용하여 문제를 푸는 방법도 있다. 

 

*링크는 에라토스테네스의 체를 사용하여 소수를 구한 문제이다. 

[파이썬]프로젝트 오일러 #7 (tistory.com)

[파이썬]프로젝트 오일러 #7