에라토스테네스의 체

• 2부터 N까지의 자연수 배열을 생성
• 배열에서 지워지지 않은 수 중 가장 작은 수를 소수로 선택
• 그 수의 배수를 배열에서 모두 제거
• 이 과정을 반복
• 남은 수가 모두 소수

→ **O(N) ****최적화된 방법 (제곱근까지만 탐색) → O(N log log N)

037 소수 구하기

• 에라토스테네스의 체
  • 크기가 N+1인 배열을 생성하여 각 인덱스를 수 자체로 초기화
  • 1은 소수가 아니므로 제거
  • 2부터 시작하여 자기 자신을 제외한 배수는 전부 제거
  • 제곱근 N까지 탐색하면 충분함
  • 배열에 남아 있는 값들이 소수임
• 소수를 찾을 때는 제곱근까지만 확인해도 충분
  • 예: 16의 배수를 찾기 위해선 4까지만 확인해도 충분 (4×4=16)

038 거의 소수 구하기

• 소수의 거듭제곱 형태이지만 소수는 아닌 수 = ‘거의 소수’
  • 시간 복잡도 줄이기 위해 소수는 √B 까지만 탐색
• 1 ~ 10⁷까지의 소수를 먼저 구함 (에라토스테네스의 체)
• 각 소수 p에 대해 p^2, P^3,.. 등 p의 거듭제곱이 B를 넘지 않을 때까지 곱하며
• 그 값이 A 이상 B 이하이면 카운트

039 소수 & 팰린드롬 수 중에서 최소값 찾기

• 에라토스테네스의 체로 소수 구하기
  • 1부터 1,000,000까지 배열을 초기화하고, 소수가 아닌 수를 제거
• N부터 시작해서 증가시키며
  • 해당 수가 소수인지 확인하고
  • 팰린드롬인지 판별하여 조건 만족 시 출력하고 종료
• 팰린드롬 판별 방법
  • String.valueOd(number).toCharArray()로 변환
  • 양 끝에서 포인터를 이동하며 값이 같지 않으면 팰린드롬 아님

040 제곱이 아닌 수 찾기

• min부터 max까지 하나씩 검사하면서 제곱수로 나눠지는지 확인 → 비효율적, 시간 초과 가능
• 제곱수의 배수를 미리 마킹하고 제외하는 방식 사용

  • 2^2, 3^2, ..., sqrt(max)^2까지의 제곱수를 기준으로

    각 제곱수에 대해 [min, max]범위에서 해당 제곱수의 배수들을 true로 체크

  • check 배열에서 flase인 값들의 개수를 세면, 그것이 ‘제곱이 아닌 수’의 개수

• 마킹 방식은 ‘에라토스테네스의 체’와 비슷한 논리
• max는 최대 10^12까지 되므로 long 사용

1부터 N까지의 정수 중에서 N과 서로소인 자연수의 개수를 의미

• φ(6) = 2 → 1, 5는 6과 서로소
• φ(8) = 4 → 1, 3, 5, 7

계산 원리

• 1부터 N까지의 수를 배열에 저장한다.

• 배열에서 소수의 배수들을 순차적으로 지워가며 계산한다.

  (에라토스테네스의 체 방식과 유사)

• 소수 p를 만날 때마다 배열[k] = 배열[k]-배열[k] / p를 적용한다.

  즉, φ(N) = N × (1 - 1/p₁) × (1 - 1/p₂) × ...

  → 여기서 p₁, **p₂, …**는 N의 서로 다른 소인수들

  N = 15
  초기: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 → 총 15개  
  2의 배수 제거 → 2 4 6 8 10 12 14 제거  
  3의 배수 제거 → 3 6 9 12 15 제거  
  5의 배수 제거 → 5 10 15 제거  
  → 남은 수: 1, 7, 11, 13 (15와 서로소)
  → φ(15) = 8
  

• 수학적 공식

  • 어떤 수 N이 소인수 분해되어

    N = p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ 이면

    φ(N) = N × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ)

041 오일러 피 함수 구현하기

• 1 ≤ k ≤ n중에서 n과 서로소인 수의 개수

  ⇒ 서로소가 아닌 수들은 소수 p의 배수이기 때문에 그만큼을 빼주는 방식으로 구함

• result = n으로 초기화

• 2부터 sqrt(n)까지의 소수 p에 대해

  • n이 p로 나누어 떨어지면:
    • result = result - result / p
    • n에서 해당 소수를 모두 제거 (while n % p == 0)

• 반복 끝나고 n > 1이라면 마지막 남은 소인수 존재

  • result = result - result / n

두 수의 최대공약수(GCD)를 빠르고 효율적으로 구하는 알고리즘

GCD(Greatest Common Divisor)

• 두 수의 공통된 약수 중 가장 큰 수를 의미
  • gcd(270, 192) = 6
  • gcd(10, 4) = 2

큰 수를 작은 수로 나눠서 나온 나머지를 계속 나누는 방식

• 큰 수를 작은 수로 MOD 연산 (나머지 구하기)

• 이전 단계의 작은 수를 큰 수로 나머지를 작은 수로 바꿔서 다시 반복

• 나머지가 0이 되면 그때의 작은 수가 바로 최대공약수(GCD)!

  gcd(a, b) = gcd(b, a % b) → a % b == 0이면 b가 최대공약수!

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

042 최소공배수 구하기

• 최소공배수 공식: LCM(A, B) = (A * B) / GCD(A, B)

  • GCD(A, B): A와 B의 최대공약수
  • 곱을 최대공약수로 나누면 가장 작은 공배수가 됨

• 최대공약수(GCD) 구하는 법: 유클리드 호제법

  gcd(a, b) = gcd(b, a % b) b가 0이면 gcd는 a

043 최대 공약수 구하기

• 실제 숫자값은 111…1 형태의 수 (모든 자리가 1)
• 숫자가 아닌 자릿수의 최대공약수를 구해서
  • 3, 6 → gcd(3, 6) = 3
• 그 길이만큼 1을 반복해서 출력

044 칵테일 만들기