1747번: 소수&팰린드롬
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고,
www.acmicpc.net
#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
소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요. n = 2**20 primes = [] #소수를 담을 list table = [False, False] + [True]*(n-1) for i in range(2, n+1): if table[i]: pr
daybreakfrontline21.tistory.com
'CodingTest > 백준' 카테고리의 다른 글
[c++] 백준 - 2920번: 음계 | char배열과 String클래스를 사용한 문자열비교 (0) | 2023.04.12 |
---|---|
[c++] 백준 - 5597번: 과제 안 내신 분..? (0) | 2023.04.11 |
[c++] 백준 - 5800번: 성적 통계 (0) | 2023.03.25 |
[c++] 백준 - 2204번: 도비의 난독증 테스트 (수정) (0) | 2023.03.23 |
[C언어] 백준 - 4673번: 셀프 넘버 (0) | 2023.02.03 |