작업이 [1, N] 범위에서 숫자가 가질 수 있는 고유한 소인수의 최대 수를 찾는 것이므로 N이 제공됩니다.
이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -
입력 - N=100
출력 - 3
설명 − [1, 100]의 범위에서 30을 취합니다.
30 =3 * 2 * 5 =고유한 소인수. 따라서 [1, 100]의 범위에서 최대 3개의 고유한 요소를 찾을 수 있습니다.
입력 - N=300
출력 - 4
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
MaxPrime() 함수에서 먼저 (N <2)인지 확인합니다. 그렇다면 단순히 0을 반환하고, 그렇지 않으면 계속 진행하십시오.
-
그런 다음 에라토스테네스의 체를 사용하여 주어진 숫자 N 이전의 모든 소수를 찾습니다.
-
int 유형의 두 변수 pro=1 및 max=0을 초기화하여 제품과 최종 답변을 각각 저장합니다.
-
에라토스테네스의 체 안에서 우리는 곱이 N보다 작아질 때까지 첫 번째 소수 집합을 곱할 것입니다. − pro=*p;
-
(pro> N)인지 확인하십시오. 그렇다면 최대값을 반환하고 최대값에 1을 더하세요.
-
체 외부에서도 최대값을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
if (N < 2)
return 0;
// Using Sieve of Eratosthenes
bool Arr[N+1];
memset(Arr, true, sizeof(Arr));
int pro = 1, max = 0;
for (int p=2; p*p<=N; p++){
if (Arr[p] == true){
for (int i=p*2; i<=N; i += p)
Arr[i] = false;
/*Multiply first set of prime numbers while product remains smaller than N*/
pro *= p;
if (pro > N)
return max;
max++;
}
}
return max;
}
//Main function
int main(){
int N = 300;
cout << MaxPrime(N);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -
4