주어진 문제에서 주어진 정수 n의 모든 제수를 출력해야 합니다.
Input: 15 Output: 1 3 5 15 Explanation Divisors of 15 are: 1,3, 5, 15 Input: 30 Output: 1 2 3 5 15 30
주어진 문제에서 n의 모든 제수를 찾기 위해 에라토스테네스의 체에서 사용된 접근 방식을 적용할 수 있습니다.
해결책을 찾기 위한 접근 방식
주어진 접근 방식에서 우리는 에라토스테네스의 체를 기반으로 하는 개념을 적용하고 n의 제수를 찾습니다.
예시
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
vector<int> divisors[100001]; // our vector containing number with all of its divisors
void findsieve(int max) { // filling data in vector divisors till 10e5
for(int i = 1; i <= max; i++) {
for(int j = i; j <= max; j += i)
divisors[j].push_back(i);
}
}
void __print(int n){ // the function to print divisors
for(auto x : divisors[n])
cout << x << " ";
cout << "\n";
}
int main() {
findsieve(100000); // we hardcode the sieve and divisors till 10e5
int n = 6; // the given n
__print(n);
n = 30; // new n
__print(n);
return 0;
} 출력
1 2 3 6 1 2 3 5 6 10 15 30
위 코드 설명
이 접근 방식에서 우리는 에라토스테네스의 체와 동일한 개념을 따릅니다. 우리는 105까지 모든 숫자의 제수를 찾습니다. q 쿼리가 제공되면 제수를 찾을 필요가 없으므로 q 쿼리를 요청할 때 시간 복잡성이 크게 줄어듭니다. 따라서 복잡성은 O(Q*N)가 됩니다. 여기서 Q는 처리하는 쿼리의 수이고 N은 n의 제수입니다.
결론
이 기사에서는 문제를 해결합니다. 에라토스테네스의 체 원리를 적용하는 n의 모든 제수를 출력하는 쿼리. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.