n보다 작은 삼차 자유수

3차 인수가 없는 숫자는 3차 인수가 없는 숫자입니다.

세제곱 인수는 세제곱이고 나머지 없이 숫자를 나누는 정수입니다.

예를 들어 8은 2의 세제곱 인수(2*2*2 = 8)이고 8을 16으로 나눈 나머지가 0이므로 8은 16의 세제곱 인수입니다.

그러므로 8이나 16은 모두 세제곱수가 아닌 숫자입니다.

문제 설명

주어진 숫자 n보다 작은 큐브리스 숫자를 모두 찾아보세요.

Example

은 다음과 같이 번역됩니다.

Example

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

1, 8, 16은 목록에 없습니다. 1과 8은 그 자체가 세제곱수이고, 16은 8의 배수이기 때문입니다.

이 문제를 해결하는 방법에는 두 가지가 있습니다.

방법 1: 폭력적인 방법

무차별 대입 크래킹 방법은 다음과 같습니다.

• n까지 모든 숫자를 반복합니다.

• 각 숫자에 대해 모든 약수를 반복합니다.

• 어떤 숫자의 약수가 세제곱 숫자라면 그 숫자는 세제곱이 없는 숫자가 아닙니다.

• 그렇지 않고, 이 숫자의 약수가 3차가 아닌 경우, 이는 3차가 없는 숫자입니다.

• 숫자를 인쇄하세요.

Example

은 다음과 같이 번역됩니다.

Example

이 접근 방식의 프로그램은 다음과 같습니다 −

아래는 주어진 숫자 n보다 작은 모든 큐브리스 숫자를 인쇄하는 C++ 프로그램입니다.

으아아아

출력

으아아아

방법 2: 에라토스테네스의 체 기법

이 문제를 해결하는 효율적인 방법은 에라토스테네스의 체라는 개념이 될 것입니다.

주어진 한계보다 작은 소수를 찾는 데 사용됩니다. 여기서는 삼차수가 아닌 숫자를 필터링하여 솔루션을 얻습니다.

방법은 다음과 같습니다−

• 크기 n의 부울 목록을 만듭니다.

• 모든 숫자를 true로 표시하세요. 이는 현재 모든 숫자를 큐브리스로 표시했음을 의미합니다.

• n보다 작은 가능한 모든 큐브를 탐색합니다.

• n보다 작은 삼차수의 모든 배수를 탐색합니다.

• 목록에 있는 모든 배수를 false로 표시하세요. 이 숫자는 큐브 프리가 아닙니다.

• 목록을 반복해 보세요. 목록에서 여전히 참인 숫자를 인쇄하세요.

• 출력에는 n보다 작은 모든 큐브리스 숫자가 포함됩니다.

Example

은 다음과 같이 번역됩니다.

Example

이 접근 방식의 프로그램은 다음과 같습니다 −

다음은 에라토스테네스의 체를 사용하여 주어진 숫자 n보다 작은 모든 큐브리스 숫자를 인쇄하는 C++ 프로그램입니다.

으아아아

출력

으아아아

이 기사는 n보다 작은 큐브리스 숫자를 찾는 문제를 해결합니다. 우리는 두 가지 방법, 즉 무차별 대입 방법과 에라토스테네스의 체를 이용한 효율적인 방법을 보았습니다.

C++ 프로그램은 이 두 가지 방법의 구현을 제공합니다.

위 내용은 n보다 작은 삼차 자유수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!