Для данного числа N, как я могу найти x, S.T произведение (x и числа факторов на x) = N?
чтобы найти факторы числа, я использую функцию void primeFactors(int n)
# include <stdio.h>
# include <math.h>
# include <iostream>
# include <map>
using namespace std;
// A function to print all prime factors of a given number n
map<int,int> m;
void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n%2 == 0)
{
printf("%d ", 2);
m[2] += 1;
n = n/2;
}
// n must be odd at this point. So we can skip one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i+2)
{
// While i divides n, print i and divide n
while (n%i == 0)
{
int k = i;
printf("%d ", i);
m[k] += 1;
n = n/i;
}
}
// This condition is to handle the case whien n is a prime number
// greater than 2
if (n > 2)
m[n] += 1;
printf ("%d ", n);cout << endl;
}
/* Driver program to test above function */
int main()
{
int n = 72;
primeFactors(n);
map<int,int>::iterator it;
int to = 1;
for(it = m.begin(); it != m.end(); ++it){
cout << it->first << " appeared " << it->second << " times "<< endl;
to *= (it->second+1);
}
cout << to << " total facts" << endl;
return 0;
}
Вы можете проверить это здесь. Test case n = 72,
http://ideone.com/kaabO0
Как решить вышеупомянутую проблему, используя выше алгоритм. (Можно ли оптимизировать больше?). Я должен учитывать и большое количество.
Что я хочу сделать ..
Возьмите пример для N = 864мы нашли X = 72 как (72 * 12 (количество факторов)) = 864)
Решение
Для больших чисел существует алгоритм первичной факторизации, но на самом деле он редко используется в соревнованиях по программированию.
Я объясняю 3 метода, и вы можете реализовать с помощью этого алгоритма.
Если вы реализовали, предлагаю решить Эта проблема.
Примечание. В этом ответе я использую целое число Q для количества запросов.
O (Q * sqrt (N)) решение для запроса
Временная сложность вашего алгоритма O(n^0.5),
Но вы реализуете с int (32-бит), поэтому вы можете использовать длинные длинные целые числа.
Вот моя реализация: http://ideone.com/gkGkkP
O (sqrt (maxn) * log (log (maxn)) + Q * sqrt (maxn) / log (maxn)) алгоритм
Вы можете уменьшить количество циклов, потому что составные числа не нужны для целого числа i.
Таким образом, вы можете использовать только простые числа в цикле.
Алгоритм:
- Рассчитать все простые числа <= sqrt (n) с ситом Эратосфена. Временная сложность O (sqrt (maxn) * log (log (maxn))).
- В запросе цикл для i (i <= sqrt (n) и i — простое число). Допустимое целое число i равно sqrt (n) / log (n) с теоремой о простых числах, поэтому сложность времени составляет O (sqrt (n) / log (n)) на запрос.
Более эффективный алгоритм
В мире есть более эффективный алгоритм, но он не часто используется в соревнованиях по программированию.
Если вы выберете «Алгоритм целочисленной факторизации» в Интернете или в википедии, вы можете найти алгоритм, например, сито Полларда или поле общего числа.
Другие решения
Хорошо, я покажу вам код.
# include <stdio.h>
# include <iostream>
# include <map>
using namespace std;
const long MAX_NUM = 2000000;
long prime[MAX_NUM] = {0}, primeCount = 0;
bool isNotPrime[MAX_NUM] = {1, 1}; // yes. can be improve, but it is useless when sieveOfEratosthenes is end
void sieveOfEratosthenes() {
//@see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
for (long i = 2; i < MAX_NUM; i++) { // it must be i++
if (!isNotPrime[i]) //if it is prime,put it into prime[]
prime[primeCount++] = i;
for (long j = 0; j < primeCount && i * prime[j] < MAX_NUM; j++) { /*foreach prime[]*/
// if(i * prime[j] >= MAX_NUM){ // if large than MAX_NUM break
// break;
// }
isNotPrime[i * prime[j]] = 1; // set i * prime[j] not a prime.as you see, i * prime[j]
if (!(i % prime[j])) //if this prime the min factor of i,than break.
// and it is the answer why not i+=( (i & 1) ? 2 : 1).
// hint : when we judge 2,prime[]={2},we set 2*2=4 not prime
// when we judge 3,prime[]={2,3},we set 3*2=6 3*3=9 not prime
// when we judge 4,prime[]={2,3},we set 4*2=8 not prime (why not set 4*3=12?)
// when we judge 5,prime[]={2,3,5},we set 5*2=10 5*3=15 5*5=25 not prime
// when we judge 6,prime[]={2,3,5},we set 6*2=12 not prime,than we can stop
// why not put 6*3=18 6*5=30 not prime? 18=9*2 30=15*2.
// this code can make each num be set only once,I hope it can help you to understand
// this is difficult to understand but very useful.
break;
}
}
}
void primeFactors(long n)
{
map<int,int> m;
map<int,int>::iterator it;
for (int i = 0; prime[i] <= n; i++) // we test all prime small than n , like 2 3 5 7... it musut be i++
{
while (n%prime[i] == 0)
{
cout<<prime[i]<<" ";
m[prime[i]] += 1;
n = n/prime[i];
}
}
cout<<endl;
int to = 1;
for(it = m.begin(); it != m.end(); ++it){
cout << it->first << " appeared " << it->second << " times "<< endl;
to *= (it->second+1);
}
cout << to << " total facts" << endl;
}
int main()
{
//first init for calculate all prime numbers,for example we define MAX_NUM = 2000000
// the result of prime[] should be stored, you primeFactors will use it
sieveOfEratosthenes();
//second loop for i (i*i <= n and i is a prime number). n<=MAX_NUM
int n = 72;
primeFactors(n);
n = 864;
primeFactors(n);
return 0;
}
Мой лучший выстрел в исполнении, не получая за борт со специальными алгоритмами.
Erathostenes ‘sive — сложность ниже O (N * log (log (N))) — потому что внутренний j цикл начинается с i*i вместо i,
#include <vector>
using std::vector;
void erathostenes_sieve(size_t upToN, vector<size_t>& primes) {
primes.clear();
vector<bool> bitset(upToN+1, true); // if the bitset[i] is true, the i is prime
bitset[0]=bitset[1]=0;
// if i is 2, will jump to 3, otherwise will jump on odd numbers only
for(size_t i=2; i<=upToN; i+=( (i&1) ? 2 : 1)) {
if(bitset[i]) { // i is prime
primes.push_back(i);
// it is enough to start the next cycle from i*i, because all the
// other primality tests below it are already performed:
// e.g:
// - i*(i-1) was surely marked non-prime when we considered multiples of 2
// - i*(i-2) was tested at (i-2) if (i-2) was prime or earlier (if non-prime)
for(size_t j=i*i; j<upToN; j+=i) {
bitset[j]=false; // all multiples of the prime with value of i
// are marked non-prime, using **addition only**
}
}
}
}
Теперь факторинг на основе primes (установить в отсортированный вектор). Перед этим давайте рассмотрим миф о sqrt быть дорогим, но большая куча умножений — нет.
Прежде всего, отметим, что sqrt не тот дороже больше: на старых процессорах (x86 / 32b) это было в два раза дороже, чем деление (и modulo операция является деление), на более новых архитектурах затраты процессора равны. Поскольку факторизация это все о % операции снова и снова, все еще можно рассмотреть sqrt время от времени (например, если и когда он используется, это экономит время процессора).
Например, рассмотрим следующий код для N=65537 (который является 6553-м простым), предполагая primes имеет 10000 записей
size_t limit=std::sqrt(N);
size_t largestPrimeGoodForN=std::distance(
primes.begin(),
std::upper_limit(primes.begin(), primes.end(), limit) // binary search
);
// go descendingly from limit!!!
for(int i=largestPrimeGoodForN; i>=0; i--) {
// factorisation loop
}
У нас есть:
- 1 кв.м. (равно 1
modulo), - 1 поиск в
10000записи — максимум 14 шагов, каждая из которых включает 1 сравнение, 1 деление на 2 с сдвигом вправо и 1 увеличение / уменьшение — так скажем, стоимость равна 14-20 умножениям (если когда-либо) - 1 разница из-за
std::distance,
Итак, максимальная стоимость — 1 див и 20 мул? Я щедрый.
На другой стороне:
for(int i=0; primes[i]*primes[i]<N; i++) {
// factorisation code
}
Выглядит намного проще, но как N=65537 прост, мы пройдем весь цикл до i=64 (где мы найдем первое простое число, которое приведет к разрыву цикла) — всего 65 умножений.
Попробуйте это с большим числом простых чисел, и я гарантирую вам, что стоимость 1 sqrt + 1 двоичного поиска лучше использовать цикл ЦП, чем все умножения на пути в более простой форме цикла рекламируется как лучшее решение производительности
Итак, вернемся к факторизационному коду:
#include <algorithm>
#include <math>
#include <unordered_map>
void factor(size_t N, std::unordered_map<size_t, size_t>& factorsWithMultiplicity) {
factorsWithMultiplicity.clear();
while( !(N & 1) ) { // while N is even, cheaper test than a '% 2'
factorsWithMultiplicity[2]++;
N = N >> 1; // div by 2 of an unsigned number, cheaper than the actual /2
}
// now that we know N is even, we start using the primes from the sieve
size_t limit=std::sqrt(N); // sqrt is no longer *that* expensive,
vector<size_t> primes;
// fill the primes up to the limit. Let's be generous, add 1 to it
erathostenes_sieve(limit+1, primes);
// we know that the largest prime worth checking is
// the last element of the primes.
for(
size_t largestPrimeIndexGoodForN=primes.size()-1;
largestPrimeIndexGoodForN<primes.size(); // size_t is unsigned, so after zero will underflow
// we'll handle the cycle index inside
) {
bool wasFactor=false;
size_t factorToTest=primes[largestPrimeIndexGoodForN];
while( !( N % factorToTest) ) {
wasFactor=true;// found one
factorsWithMultiplicity[factorToTest]++;
N /= factorToTest;
}
if(1==N) { // done
break;
}
if(wasFactor) { // time to resynchronize the index
limit=std::sqrt(N);
largestPrimeIndexGoodForN=std::distance(
primes.begin(),
std::upper_bound(primes.begin(), primes.end(), limit)
);
}
else { // no luck this time
largestPrimeIndexGoodForN--;
}
} // done the factoring cycle
if(N>1) { // N was prime to begin with
factorsWithMultiplicity[N]++;
}
}