📌 오일러 피 함수 P[N]란?오일러 피 함수 'φ(N)'은 1부터 N까지의 자연수 중에서 N과 서로소인 자연수의 개수를 구하는 함수서로소란 두 수의 최대공약수(GCD)가 1인 경우를 의미예를 들어, φ(6) = 2 ➡️ 1과 5가 6과 서로소이기 때문😊  📌  오일러 피 함수의 핵심 이론✨오일러 피 함수는 에라토스테네스의 체와 유사한 방식이라고 생각할 수 있다.1️⃣ 구하고자 하는 범위만큼 배열 초기화P[i]=i로 초기화하여 각 숫자 i에 대해 일단 후보 값을 그대로 설정2️⃣ 소수인 경우만 처리2부터 시작하여 P[i]=i인 경우, 해당 숫자는 소수이때, 현재 선택된 숫자 K의 배수에 해당하는 값들을 업데이트업데이트 방식:P[i]=P[i]−P[i]/K (소수 K에 대해 모든 배수 i에 적용)3️⃣..

📌 소수(Prime Number)란?소수는 자신보다 작은 두 개의 자연수를 곱해 만들 수 없는, 1보다 큰 자연수를 말한다.즉, 1과 자기 자신 외에는 약수가 존재하지 않는 수예) 2, 3, 5, 7, 11, 13, ... 📌  소수 구하기의 핵심 이론✨💡에라토스테네스의 체 원리소수를 구할 때 가장 널리 사용되는 알고리즘! 빠르고 효율적으로 소수를 찾을 수 있다. 🌟 1️⃣ 구하고자 하는 소수의 범위만큼 1차원 배열 생성배열의 각 값을 "소수인지 아닌지"를 나타내는 플래그로 사용한다.예를 들어, true면 소수, false면 소수가 아니다.2️⃣ 2부터 시작해서, 현재 숫자가 소수일 때, 그 배수들을 모두 제거배수는 소수가 될 수 없으므로 지워준다.단, 처음 선택한 숫자는 지우지 않음!3️⃣ 다음..