소수(15)
-
백준 1747 파이썬 에라토스테네스의 체를 이용 팰린드롬
백준 1747 - 소수&팰린드롬 문제 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 답안 코드 : import math N = int(input()) A = [0] * (10000001) for i in range(2, len(A)): A[i] = i for i in range(2, int(math.sqrt(len(A)) + 1)): # 제곱근까지만 수행 if A[i] == 0: continue for j..
2024.05.29 -
백준 2023 파이썬 DFS 재귀함수
백준 2023 - 신기한 소수 문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 답안 코드 : import sys sys.setrecursionlimit(10000) input = sys.stdin.readline N = int(input()) def isPrime(num): for i in range(2, int(num / 2 + 1)): if num % i == 0: return False return True def DFS(..
2024.05.14 -
백준 13909 파이썬 한 줄 풀이
백준 19309 - 창문닫기문제https://www.acmicpc.net/problem/13909 13909번: 창문 닫기서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째www.acmicpc.net답안 코드 :import sysN = int(sys.stdin.readline())result = 0x = 1while x * x 백준 / 문제 / 단계별로 풀어보기 / 15단계 약수, 배수와 소수 2생각 :# N = int(input())# open_windows = [0] * N # 초기에 모든 창문은 닫혀있음# for person in range(1, N..
2024.04.28 -
백준 4938 파이썬 에라토스테네스의 체
백준 4938 - 베르트랑 공준문제https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼www.acmicpc.net답안 코드 :while True: n = int(input()) if n == 0: break # 에라토스테네스의 체를 활용한 소수 판별 is_prime = [True] * (2 * n + 1) is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님 for i in range(..
2024.04.27 -
백준 1929 파이썬 에라토스테네스의 체
백준 1929 - 소수 구하기문제https://www.acmicpc.net/problem/1929 1929번: 소수 구하기첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.www.acmicpc.net답안 코드 :# 에라토스테네스의 체# 입력 받기m, n = map(int, input().split())# 소수를 저장하는 리스트primes = []# 2부터 n까지의 수를 모두 소수라 가정하고 시작is_prime = [True] * (n + 1)is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님# 에라토스테네스의 체 알고리즘for i in range(2, int(..
2024.04.26 -
백준 4134 파이썬
백준 4134 - 다음 소수문제https://www.acmicpc.net/problem/4134 4134번: 다음 소수정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.www.acmicpc.net답안 코드 :import math# 소수 판별 함수def is_prime(num): if num 백준 / 문제 / 단계별로 풀어보기 / 15단계 약수, 배수와 소수 2생각 :# √N까지만 나눠서 소수를 판별하는 문제 # n부터 시작해서 하나씩 증가시키면서 소수인지를 판별하고, # 소수일 경우 해당 값을 출력하고 반복문을 종료 # 브루트포스로 소수를 찾기
2024.04.25