Факторизация всех целых чисел от 1 до 20 в их простые разложения. Например, коэффициент 18 равен 18 = 3 ^ 2 * 2. Теперь для каждого простого числа p, которое появляется в простой факторизации некоторого целого числа в диапазоне от 1 до 20, найдите максимальный показатель, который он имеет среди всех этих простых факторизации. Например, простое 3 будет иметь показатель степени 2, потому что оно появляется при факторизации 18 как 3 ^ 2, и если оно появилось в любой простой факторизации с показателем 3 (то есть 3 ^ 3), это число будет должно быть не менее 3 ^ 3 = 27, что выходит за пределы диапазона от 1 до 20. Теперь соберите все эти простые числа с соответствующими им показателями, и у вас есть ответ.
Итак, в качестве примера, давайте найдем наименьшее число, равномерно делимое на все числа от 1 до 4.
2 = 2^1
3 = 3^1
4 = 2^2
Появляются простые числа 2 и 3. Отметим, что максимальный показатель 2 равен 2, а максимальный показатель 3 равен 1. Таким образом, наименьшее число, которое равномерно делится на все числа от 1 до 4, равно 2 ^ 2 * 3 = 12.
Вот относительно простая реализация.
#include <iostream>
#include <vector>
std::vector<int> GetPrimes(int);
std::vector<int> Factor(int, const std::vector<int> &);
int main() {
int n;
std::cout << "Enter an integer: ";
std::cin >> n;
std::vector<int> primes = GetPrimes(n);
std::vector<int> exponents(primes.size(), 0);
for(int i = 2; i <= n; i++) {
std::vector<int> factors = Factor(i, primes);
for(int i = 0; i < exponents.size(); i++) {
if(factors[i] > exponents[i]) exponents[i] = factors[i];
}
}
int p = 1;
for(int i = 0; i < primes.size(); i++) {
for(int j = 0; j < exponents[i]; j++) {
p *= primes[i];
}
}
std::cout << "Answer: " << p << std::endl;
}
std::vector<int> GetPrimes(int max) {
bool *isPrime = new bool[max + 1];
for(int i = 0; i <= max; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false;
int p = 2;
while(p <= max) {
if(isPrime[p]) {
for(int j = 2; p * j <= max; j++) {
isPrime[p * j] = false;
}
}
p++;
}
std::vector<int> primes;
for(int i = 0; i <= max; i++) {
if(isPrime[i]) primes.push_back(i);
}
delete []isPrime;
return primes;
}
std::vector<int> Factor(int n, const std::vector<int> &primes) {
std::vector<int> exponents(primes.size(), 0);
while(n > 1) {
for(int i = 0; i < primes.size(); i++) {
if(n % primes[i] == 0) {
exponents[i]++;
n /= primes[i];
break;
}
}
}
return exponents;
}
Пример вывода:
Enter an integer: 20
Answer: 232792560