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 중국어 웹사이트의 기타 관련 기사를 참조하세요!