반응형 백준알고리즘/기본 수학26 (Python/🥈1)백준 알고리즘 9020번: 골드바흐의 추측 문제 출처:https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 잘못된 풀이: array = list() for i in range(2,10000): count = 0 for j in range(2,i): if i % j == 0: count += 1 break if count == 0: array.append(i) T=int(input()) for i in range(T): n = int(input()) a = int(n//2).. 2022. 5. 17. (Python/🥈2)백준 알고리즘 4948번: 베르트랑 공준 문제 출처:https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이: array = list() for i in range(2, 246913): # 범위 설정 count = 0 for j in range(2, int(i**0.5)+1): # 2n의 제곱근 if i % j == 0: # 소수 아닌거 찾고 count += 1 # 소수면 카운트 올림 break if count == 0: # 소수 이면 array.append(i) # 리스트에 추가.. 2022. 5. 17. (Python/🥈3)백준 알고리즘 1929번: 소수 구하기 문제 출처:https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 틀린 풀이: M,N = input().split() M = int(M) N = int(N) # M,N = map(int,input().split()) for i in range(M,N+1): #3부터 16까지 if i != 1: for k in range(2,i): if i % k ==0: break else: print(i) 처음에 이렇게 작성해서 답은 나오지만 시간초과가 나왔다. 이중포문을 사용해 빅오가 O(n^2.. 2022. 5. 17. (Python/🥈5)백준 알고리즘 11653번: 소인수분해 문제 출처:https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이: N = int(input()) i = 2 # 제일 작은 나누는 수 선언 while N != 1: # 입력받은 수 1이 아닐떄 if N%i ==0: # N 나누기 i 의 몫이 0 >> 즉 2의배수일때 N /= i # N은 2로 나누고 다시 N에 저장 print(i) # 2출력 else: # 2의 배수가 아니면 i +=1 # 최소공배수를 +1 if i>N: # 쭉 진행하다가 최소공배수보다 바뀌는 N보다 클떄 break # for문 탈출 다른 풀이: n = int(input()) d = 2 while d.. 2022. 5. 17. (Python/🥈5)백준 알고리즘 2581번: 소수 문제 출처:https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이: M = int(input()) N = int(input()) sum = 0 list = list() for i in range(M,N+1): if i != 1: for k in range(2,i): if i % k ==0: break else: sum += i list.append(i) print(sum,min(list)) 처음에 이렇게 했더니 런타임 에러가 났다. 확인해보니 -1 나오는게.. 2022. 5. 16. (Python/🥈4)백준 알고리즘 1978번: 소수 찾기 문제 출처:https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이: N = int(input()) array = list(map(int,input().split())) count = 0 for i in array: # array에 있는 숫자 빼옴 if i != 1: # 1이 아닐떄 실행 for k in range(2,i): # k는 1과 자기자신을 제외한 수로 나눴을때 if i % k ==0: # 나눠지는게 있으면 브레이크 하고 나옴 break else: #나눠지는게 없으면 count +=1 # count +1 p.. 2022. 5. 16. 이전 1 다음 반응형
