Для заданного числа N, как найти x, S.T произведение (x и нет факторов на x) = N?

Question

найти факторы числа, я использую функцию 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

Как решить проблему выше, используя выше algo. (Можно ли его оптимизировать больше?). Я должен также рассмотреть большие числа.

Что я хочу сделать .. Возьмем пример для N = 864, мы обнаружили, X = 72, как (72 * 12 (нет. Факторов)) = 864)

Answer 1

Существует простой алгоритм факторизации- для больших чисел, но на самом деле он не часто используется в конкурсах программирования.
Я объясняю 3 метода, и вы можете реализовать этот алгоритм.
Если вы осуществили, я предлагаю решить this problem.
Примечание: В этом ответе я использую целое число Q для количества запросов.
раствор

O (Q * SQRT (N)) на запрос
временная сложность вашего алгоритма является O(n^0.5).
Но вы реализуете с помощью int (32-bit), поэтому вы можете использовать длинные длинные целые числа.
Вот моя реализация: http://ideone.com/gkGkkP

O (SQRT (maxn) * журнал (журнал (maxn)) + Q * SQRT (maxn)/журнал (maxn)) алгоритм
Вы можете уменьшить количество циклов потому что составные числа не обязательны для целого числа i.
Итак, вы можете использовать только простые числа в цикле.

Алгоритм:

1. Вычислить все простые числа < = SQRT (п) с ситом Эратосфена в. Сложность времени - O (sqrt (maxn) * log (log (maxn))).
2. В запросе цикл для i (i < = sqrt (n) и i - простое число). Действительное целое число i относится к sqrt (n)/log (n) с теоремой о простых числах, поэтому временная сложность O (sqrt (n)/log (n)) для каждого запроса.

Более эффективный алгоритм
Есть более эффективный алгоритм в мире, но он часто не используется в соревнованиях по программированию.
Если вы проверите алгоритм «Целочисленный алгоритм факторизации» в Интернете или в википедии, вы можете найти алгоритм, например, как полевое поле Полларда-ро или общее число.

Answer 2

Мой лучший выстрел в исполнении, не выходя за борт с особыми альгосами.

The Erathostenes' seive - сложность ниже является O (N * журнала (журнал (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 is not that expensive anymore: на старых CPU-эс (x86/32b) это было в два раза дороже, чем разделение (и modulo операции является деление), на новых архитектурах CPU затраты равны. Так как факторизация - это все о % операциях снова и снова, все равно можно рассматривать sqrt сейчас (например, если и когда он используется, это экономит процессорное время).

Для примера рассмотрим следующий код для N=65537 (который является 6553-й прайм) предполагая, что primes имеет 10000 entries

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 SQRT (равный 1 modulo) ,
• 1 поиск по 10000 записей - при максимальных 14 шагах, каждый из которых включает в себя 1 сравнение, 1 сменное смещение на 2 и 1 приращение/декремент - с o допустим, что стоимость равна 14-20 умножениям (если когда-либо)
• 1 разница из-за std::distance.

Итак, максимальная стоимость - 1 div и 20 muls? Я щедр.

С другой стороны:

for(int i=0; primes[i]*primes[i]<N; i++) { 
    // factorisation code 
} 

выглядит гораздо проще, но, как N=65537 первична, мы будем проходить через весь цикл до i=64 (где мы находим первое простое число, которое вызывает цикл сломать) - всего 65 умножений.
Попробуйте это с более высоким простым номером, и я гарантирую, что стоимость 1 sqrt + 1binary search лучше использовать процессорный цикл, чем все умножения на пути в более простой форме цикла. рекламируется как лучшее решение производительности.

---

Итак, вернемся к коду факторизации:

#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]++; 
    } 
} 

Answer 3

Ну, я покажу вам код.

# 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; 
}