📚 목차

요약

1. 오일러 피

1. 오일러 피

• 오일러 피 함수 P[N]이란 1부터 N까지의 수들이 갖는 각각의 서로소인 자연수의 개수를 의미한다.

2. 오일러 피의 원리

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스값으로 초기화한다.
2. 2부터 시작하여 2의 배수마다 현재 배열의 값과 인덱스가 같으면(=소수면) 현재 선택된 숫자의 배수에 해당하는 수를 배열의 끝까지 탐색하며 배열값 = 배열값-(배열값/인덱스) 연산을 수행한다.
3. 배열의 끝까지 2를 반복하여 오일러 피 함수를 완정한다.

3. 오일러 피의 예시

1. 구하고자하는 범위까지 배열을 생성한다.