반복적 인 등가 재귀 알고리즘

Question

나는이 프로그램을 상응하는 반복으로 수정하려고하지만 아직까지는 아직 초보자이기 때문에 숫자를 주요 인자로 분해하는 알고리즘을 사용하기 때문에 매우 어려워진다. 여기 코드 :

#include <iostream> 
#include <map> 
#include <cmath> 

std::map< int, std::pair<int, int> > decompositions; 

void descompon_number(int num, int root, int i = 2) 
{ 
    auto iterator = decompositions.find(num); 
    if (iterator == decompositions.end()) 
    { 
     if (num > 1 && i <= root) 
     { 
      if (num % i == 0) 
      { 
       int n = num/i; 
       decompositions[num] = std::make_pair(i, n); 
       descompon_number(n, (int) std::sqrt(n)); 
      } 
      else 
       descompon_number(num, root, i + 1); 
     } 
     else 
      decompositions[num] = std::make_pair(num, 1); 
    } 
} 

void show(int num, int factor, int exponent, int see) 
{ 
    auto pair = decompositions[num]; 
    if (num <= 1 || factor != pair.first) 
    { 
     if (see) 
      std::cout << factor; 
     if (exponent > 1 && see) 
      std::cout << "^" << exponent; 
     if (pair.first > 1 && see) 
      std::cout << " * "; 
     exponent = 0; 
    } 
    if (num > 1) 
     show(pair.second, pair.first, exponent + 1, see); 
} 

void descompon(int a, int b, int see) 
{ 
    if (a <= b) 
    { 
     descompon_number(a, (int) std::sqrt(a)); 
     if (see) 
      std::cout << a << " = "; 
     show(a, decompositions[a].first, 0, see); 
     if (see) 
      std::cout << std::endl; 
     descompon(a + 1, b, see); 
    } 
} 

int main() 
{ 
    descompon(2, 100, 1); 
    return 0; 
} 

누군가가 반복적으로 매우 복잡하지 않습니다이

Answer 1

이 주요 요인을 찾기 좀 도와 수 있습니다.

다음은 의사 코드입니다.

을 과 같은 첫 번째 n 소수의 목록으로 놓습니다.

array findPrimeFactors(m) 
    answer = new array 
    for p in P 
     while m can be divided by p 
      m = m/p 
      answer.append(p) 
     if m == 1 
      break 
    return answer 

주 : m이 소수 일 경우 빈 배열이 반환됩니다.

Answer 2

소용돌이 모양의 체를 사용하여 소수를 계산할 수 있으며 나중에 popovitsj이 게시 한 알고리즘을 사용할 수 있습니다.

다음 코드는 최적화 할 수 있지만 그 주요 목적은 진행 방법을 보여주는 것입니다.

전체 예제 :

#include <iostream> 
#include <vector> 

using namespace std; 

// Returns a vector containing the first <number> prime numbers 
vector<int> erastotenes_sieve(int number) 
{ 
    vector<int> result; 
    int *sieve = new int[number]; 
    for (int i = 0; i < number; i++) sieve[i] = 0; 


    // Traverse the sieve marking multiples. 
    for (int i = 2; i < number/2; i++) 
     for (int j = i + i; j < number; j += i) 
      sieve[j] = 1; 

    // Collect unaffected indexes, those are prime numbers. 
    for (int i = 2; i < number; i++) 
     if (!sieve[i]) 
      result.push_back(i); 

    delete [] sieve; 

    return result; 
} 

vector<int> descompon_number(int number) 
{ 
    vector<int> result; 

    if (number == 1 || number == 0) 
    { 
     result.push_back(number); 
     return result; 
    } 

    for (int &prime : erastotenes_sieve(number)) 
    { 
     while (number % prime == 0 && number != 1) 
     { 
      number /= prime; 
      result.push_back(prime); 
     } 
    } 

    return result; 
} 


int main() 
{ 
    for (auto &i : descompon_number(20)) 
    { 
     cout << i << endl; 
    } 

    return 0; 
}