104. 소수
문제
자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.
입력
입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.
출력
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
예제 입력 1
60
100
예제 출력 1
620
61
예제 입력 2
64
65
예제 출력 2
-1
<내 풀이>
first= int(input())
last= int(input())
arr=[0]*(last+1)
sosu=[0]*(last-first+1)
index=0
cnt=0
sum=0
arr[1]=1 #1꼭 직접 소수 아니라고 표시해주기
for i in range(2,last+1) :
if arr[i]==0:
for j in range(i,last+1,i) :
arr[j]=1
arr[i]=0
for i in range(first,last+1) :
if arr[i]==0:
sosu[index]=i
index+=1
cnt+=1
sum+=i #합
if cnt == 0 :
print(-1)
else :
print(sum)
print(sosu[0])
<다른 분의 풀이 or 내 틀린 풀이, 문제점>
(1) 처음에 주어진 숫자 범위 안에서의 소수들을 찾고 배열에 해당 소수 인덱스에 1을 체크해주는 것으로 하는 for 문이 있었다. 이 부분에서 나는 배열의 값이 0 이라면 for i in range(0인값, 끝까지, 0인값) 으로 해서 해당 값의 배수들을 모두 제거해주는 코드에서
for i in range(2,last+1) :
if arr[i]==0:
for j in range(i,last+1,i) :
arr[j]=1
문제가 있었다. 바로
i번째에 해당하는 아이는 소수이므로 0으로 되어있어야 하는데 range 함수가 i부터 돌다보니깐 arr[i] 아이도 1로 되는 것이었다.
그래서 위의 코드를 아래와 같이 arr[i]=0으로 다시 체크하도록 했당
for i in range(2,last+1) :
if arr[i]==0:
for j in range(i,last+1,i) :
arr[j]=1
arr[i]=1혹은 range문을 돌릴 때 range(2i, last+1, i)로 해도 될듯 하당
<반성 점>
- 항상 에라스토테네스체를 쓰자
=> 배열 만들고 0이면 그에 해당하는 배수들 체크표시 꼭~~
<배운 점>
- 배열 생성법
`arr=[0]*(배열크기)'
