백준 1644. 소수의 합 (파이썬-투 포인트, 에라토스테네스의 체를 이용해 소수 구하기)

문제를 요약하면..

N 이하의 소수 중

연속되는 소수의 합=N 이 되는 경우의 수 합 구하기

1) N 이하의 소수 구하기 --> 에라토스테네스의 체 이용

2) 합이 N이 되는 경우 찾기 --> 투 포인트 사용

​

두 종류의 코드로 작성해봤다.

첫 번째 코드는 매번 루프를 돌때마다 sum 함수를 이용해 start ~ end까지 구간의 합을 계속 구한다.

매번 sum 함수 연산이 부담스러울 까봐

두 번째 코드는 "연속적인" 소수의 합이라는 특징을 이용해

기존 합에 +end 값 또는 -start 값을 해주어 sum 함수의 부담을 줄여보았다.

즉, 부분합 코드를 sum 함수를 이용할 것인가- 첫번째 코드
부분합 코드를 기존 합계 값에 +- 할 것인가-두번째 코드
그 차이이다.

시도1. (정답)

시도2. (정답)

근데..두 코드다 정답인ㄷ

아이러니하게도 첫번째 코드의 시간이 더 짧네..?...

이 부분은 더 알아봐야겠다.

에라토스테네스의 체
https://this-programmer.tistory.com/409

위 백준 코드에서 똑같이 사용했다.

에라토스테네스의 체 구현방법 2가지로 해보았다. (위 링크 참고!!)

첫번째 코드에 사용한 것

두번째 코드에 사용한 것

◆checkpoiont!

1) 0,1은 소수가 아니다

2) 무의미한 반복 연산을 줄이기 위해 2~N이 아닌 2~N의 제곱근 까지 검사한다.

제곱근 계산

  1-  N**2

  2-  math.sqrt(N)    --단, import math 해줘야댐

3) 소수는 prime여부 리스트에서 1(True)인 것이 인덱스 값과 동일하다

4) i값이 소수라면 i의 배수는 모두 소수가 아님 -- j 반복루프 사용

 1- for j in range(i*i,N+1,i)

 2- for j in range(i+i, N+1,i)

 두 경우를 쓰는 경우가 있다. 두 표현을 해도 정답은 맞게 뜨던데..흠..   (혹시 모르니까 이부분도 다시 체크하기..)