Coding Test/Math

1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 """ 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. """ import math n=int(input()) # 에라토스테네스 체 소수구하기 a=[0]*1000..

1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 분석 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구함 주어진 소수들의 N제곱값이 A~B 범위안에 존재하는지 판별하며 갯수 체크 풀이 """ 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력 1 ≤ A ≤ B ≤ 10^14 5324 894739 183 """ import math min,max=map(int, input().split()) a..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 분석 1 ≤ M ≤ N ≤ 1,000,000 이므로 일반적인 소수 구하기 방식으로 풀면 시간 초과 발생 ➔ 에라토스테네스 채 N의 제곱근까지만 탐색하는 이유 N의 제곱근이 n일 때 N=a*b를 만족하는 a b 전부 다 n보다 클 수 없음 N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가짐 에라토스테네스의 체로 n이하의 수의 배수를 모두 제거하면 1부터 N사이의 소수를 구할 수 있음 N=16, n=4 a, b= (1,16),(2,8),(4,4)(8,2),(16,1) N보다 작..