본문 바로가기

소수

 (4)
[소수의 판별] 프로그래머스 L1 '소수 찾기' (Python) https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 1. 에라토스테네스의 체 공식으로 소수 구하기 def solution(n): answer = 0 # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * (n+1) # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in ran..
[소수의 판별] 백준 1929번 '소수 구하기' (Python) https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net N과 M의 최댓값이 1,000,000이므로 에라토스테네스의 체 알고리즘으로 풀어야 함 '''입력 예제 3 16 ''' import math n,m = map(int,input().split()) array = [True for i in range(m+1)] array[0],array[1] = 0,0 #0,1은 소수 아님 주의 for i in range(2,int(math.sqrt(m))+1): if array[i]==True: ..
[해시] 백준 15829번 'Hashing' (Python) https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 아스키코드를 정수로(ord), 정수를 아스키코드로(chr) 변환하는 함수 사용 문제에 나와있는 공식대로 코딩 ''' 5 abcde 3 zzz 1 i ''' import sys input_data = sys.stdin.readline().rstrip() L = int(input_data.split()[0]) S = input_data.split()[1] hash = dict() for idx, i..
[완전탐색] 프로그래머스 L2 '소수 찾기' (Python) https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 종이 조각으로 여러 개의 조합을 만들어야 하므로 itertools 라이브러리 사용 중복된 숫자가 나올 수 있으므로 set() 사용 소수는 에라토스테네스의 체 공식으로 찾음 from itertools import permutations from math import sqrt def solution(numbers): s = set() for i in ..
LIST

티스토리툴바