백준_6588, 17425, 6064, 1107, 14500_(PSstudy 24.03.10)

1️⃣ 백준 6618

- pseudo code

1. 에라토스테네스의 체 - 소수 리스트(prime) 구해놓음.
2. 짝수 입력 받음(n), 두 홀수의 차를 저장하는 변수(max_diff) 선언, 출력하는 두 홀수 저장하는 변수(a,b) 선언, n이 0이면 break(입력 끝났다는 뜻)
3. 무한루프 - 두 홀수 소수의 합이 짝수라는 내용 print
   <조건>
   • 3.1 : 두 홀수 소수가 1번에서 구한 소수 리스트에 포함되는지 check
   • 3.2 : 두 홀수의 차가 기존 값보다 더 크면 a, b에 저장
   • 3.0(범위) : 두 홀수 소수를 구하는 범위는 range(n-3, 4, -2)🔴 임. 두 홀수 소수의 최소 범위는 3부터~최대 범위는 n-3이며, 홀수이니 2씩 감소하며 최대범위에서 최소범위 순으로 check.
4. a와 b가 0이 아니면 n = a + b 문장 출력
   두 홀수 소수 합으로 나타낼 수 없는 경우, 즉 a와 b가 0이면 골드바흐 추측 틀렸다는 문장 print.
   (참고로, 실제 그런 경우가 있나 궁금해서 찾아봤는데, 아직 정수론에서 유명한 미해결 문제이며, 약한 추측 정도는 증명되었다고 함. 컴퓨터가 계산할 수 있는 한에서는 추측이 틀렸다는 문장을 출력할 일은 없을 것으로 보임..ㅎㅎ)

- TIL

[효율적으로 약수를 찾는 알고리즘], 약수&제곱근 간 관계 참고한 티스토리. 감사합니다.
간략 정리 : 100의 약수 중간은 10. 따라서 해당 수 제곱근까지만 약수 찾으면 됨.

- code(python)

예상 시간복잡도 :

- 스터디원과 비교, 내 코드 보완할 점, 궁금한 점

🔴부분에서, 나는 range(n-3, 4, -2)이 맞다고 생각하는데, 타 코드를 보면 range(n-3, 2, -2)로 쓴 글이 있다.. 뭐가 맞는지 모르겠다.

• 참고링크
  백준 6588, @hyeo_71 님 벨로그, 감사합니다.