시나위

www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net import sys input = sys.stdin.readline #에라토스테네스의 체로 소수를 먼저 구함 max_number= 10000 prime=[False,False,]+[True]*(max_number - 1) for i in range(2,int(max_number**0.5)+1): if prime: for j in range(2*i,max_number+1,i): prime[j]..

www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net tmp = 123456*2 prime=[False,False]+[True]*(tmp) for i in range(2,int(tmp**0.5)+1): if prime[i]: for j in range(2*i,tmp+1,i): prime[j]=False while True: n = int(input()) if n == 0: break print(prime[n+1:2*n+1].count(True)) 이번엔 에..

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()) #m, n = 3, 16 prime=[False,False,]+[True]*(n-1) for i in range(2,n+1): if prime[i]: for j in range(2*i,n+1,i): prime[j] = False if i >= m: print(i) 에라토스테네스의 체를 사용한 문제이다. 체를 사용하여 소수를 구하면서 범위 안에 있는 경우에만 출력하는 코드이다. 타인의 ..

www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net n,k=map(int,input().split()) prime=[False,False]+[True]*(n-1) index,result = 0,0 for number, val in enumerate(prime): if val: for i in range(number,n+1,number): if prime[i]: prime[i]=False index+=1 if index==k: result = i break print(result) 에라토스테네스의 체를 사용할때 항상 앞에 false 두개를 넣고 시작한..

첫번째 시도 def solution(n): answer = 0 prime_num=[] for i in range(2,n+1): for j in range(2,i+1): if (i%j==0): if (i!=j): break prime_num.append(i) answer = len(prime_num) return answer 효율이 좋지 않아서(시간초과되어서) 전체를 다 풀지 못하였다. 두번째 시도 def solution(n): answer = 0 prime_num=[] for i in range(2,n+1): chk=True for j in prime_num: if (i%j==0): # if i isnt primenum chk=False # chk changes false break if chk: # c..