728x90 반응형 소수 구하기4 [백준] 1016번 : 제곱 ㄴㄴ 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 1. 문제 설명 2. 풀이과정 min의 최댓값이 1,000,000,000,000으로 매우 큰 것 같지만 실제로는 min과 max 사이의 수들 안에서 제곱이 아닌 수를 구하는 것이므로 최대 1,000,000의 데이터만 확인하면 된다. 제곱수 판별을 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별할 때 적용해 문제를 해결한다. 2의 제곱수인 4부터 max 값까지 제곱수를 찾는다. 제곱수를 찾을 시작 .. 2024. 1. 29. [백준] 1747번 : 소수&팰린드롬 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 1. 문제 설명 2. 풀이과정 에라토스테네스의 체를 이용하여 최대 범위에 해당하는 소수를 모두 구해 놓고 소수인 수들 중 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다. 소수를 구하는 것은 에라토스테네스의 체로 쉽게 구할 수 있지만 팰린드롬 수를 판별할 때는 숫자의 값을 각 자릿수 별 리스트의 형태로 바꿔 판별해야 한다. N의 범위는 1~1,000,000인데, 정답은 N보다 같거나 커야 한다. 최대 범위를.. 2024. 1. 28. [백준] 1456번 : 거의 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 최대 범위에 해당하는 모든 소수를 구해 놓고, 구한 소수들의 N제곱값이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다. 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 최대로 소수를 탐색해야 하는데 에라토스테네스의 체를 이용하여 빠르게 소수를 먼저 구한다. 이후 구한 소수들의 N제곱값이 A와 B 범위 안에 존재하는지 판별해 거의 소수의 개수를 구하면 문제를 해결할 수 있다. 슈도코드 A(시작 수).. 2024. 1. 26. [백준] 1929번 : 소수 구하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 sys.stdin.readline() 함수를 사용하여 입력을 받기 위해 sys 모듈을 불러온다. import sys 소수를 구할 범위의 수를 입력받는다. M, N = map(int, sys.stdin.readline().split()) 함수를 구현하여 문제를 해결한다. def Func(num) 소수는 1과 자기 자신만 약수로 갖는 수를 말한다. 따라서 어떤 수를 제곱하였을 때 그 수가 소수를 판별할 수보다 크면 어떤 수보다 작은 수 중에서 나누었을 때 나누어 떨어.. 2023. 7. 9. 이전 1 다음 728x90 반응형
