Нахождение полу простого числа с использованием рекурсии c ++ - PullRequest
Новая
       3

Нахождение полу простого числа с использованием рекурсии c ++

0 голосов
/ 15 декабря 2011

есть ли способ преобразовать это в форму рекурсии? как найти неизвестные простые множители (если это полупростая)? 

semiPrime function:

bool Recursividad::semiPrimo(int x)
{
    int valor = 0;
    bool semiPrimo = false;
    if(x < 4)
    {
        return semiPrimo;
    }
    else if(x % 2 == 0)
    {
        valor = x / 2;
        if(isPrime(valor))
        {
            semiPrimo = true;
        }
    }
    return semiPrimo;
}

Редактировать: я пришел к частичному решению (не в рекурсивной форме). я знаю, что должен использовать хвостовую рекурсию, но где? 

   bool Recursividad::semiPrimo(int x){
    bool semiPrimo=false;
vector<int> listaFactores= factorizarInt(x);
vector<int> listaFactoresPrimos;
int y = 1;

for (vector<int>::iterator it = listaFactores.begin();
            it!=listaFactores.end(); ++it) {
                if(esPrimo(*it)==true){
            listaFactoresPrimos.push_back(*it);         
        }
    } 
int t=listaFactoresPrimos.front();
if(listaFactoresPrimos.size()<=1){  
    if(t*t==x){
    semiPrimo=true;
    }
}else{
    int f=0;
    #pragma omp parallel 
    {
     #pragma omp for
    for (vector<int>::iterator it = listaFactoresPrimos.begin();
            it!=listaFactoresPrimos.end(); ++it) {
                f=*it;
                int j=0;
                for (vector<int>::iterator ot = listaFactoresPrimos.begin();
            ot!=listaFactoresPrimos.end(); ++ot) {
                j=*ot;

                if((f * j)==x){
                            semiPrimo=true;         }

                }

    } 
    }
}
return semiPrimo;
}

любая помощь будет оценена

Ответы [ 3 ]

0 голосов
/ 15 декабря 2011

На самом деле ваш алгоритм не лучший способ сделать это. Если x будет больше 100, ваша программа потерпит неудачу.

Наивным алгоритмом для проверки, является ли число простым, является алгоритм пробного деления . Реализация с рекурсией: 

bool is_prime_rec(int x, int it = 2)
{
    if (it > sqrt(double(x)))
        return true;
    return x%it ? is_prime_rec(x, ++it) : false;
}

Но это будет выглядеть намного лучше, если мы заменим рекурсию циклом: 

bool is_prime(int x)
{
    if (x == 2)
        return true;
    if (x%2 == 0)
        return false;

    // speed up a bit
    for (int i = 3; i <= sqrt(double(x)); i += 2) 
        if (x%i == 0)
            return false;
    return true;
}
0 голосов
/ 15 декабря 2011

Обычный ответ для нахождения простых чисел от 1 до n - это Сито эрастонов .Но сначала вам нужно выяснить, как вы определяете, является ли число полу-простым.Вы можете поймать тривиальные случаи от 1 до 7, если хотите.После этого нужно запустить сито и проверить каждое простое число как делитель.Если это четный делитель, а частное также есть в вашем списке простых чисел, вы золотой.Если его нет в вашем списке простых чисел (и оно еще не достигнуто ситом), добавьте его в список вероятных и отметьте их, поскольку вы генерируете достаточно высокие простые числа.Как только вы найдете два простых числа, выйдите с успехом.Если вы достигнете своего числа, деленного на наименьший простой делитель, выйдите с ошибкой.

Поймай, я не могу придумать, как реализовать это в рекурсии, а не снизить производительностьТем не менее, вы можете объединить это с битом Дероберта о преобразовании в рекурсию, передавая указатели на ваши ссылочные массивы простых и вероятных значений.

0 голосов
/ 15 декабря 2011

Вы можете преобразовать цикл в рекурсию по формуле.Обратите внимание, что do_something() не обязательно должен быть вызовом одной функции;это может быть что угодно (кроме управления потоком, например break, которое изменило бы поведение цикла): 

void iterative() {
    for (int x = 0; x < 10; ++x) {
        do_something(x);
    }
}

становится 

void recursion_start() {
    recursive(0);
}

void recursive(int x) {
    if (x < 10) {
        do_something(x);
        recursive(x + 1);
    }
}

Обратите внимание, что вы можете переписать это следующим образом, который в хорошем компиляторе на самом деле будет работать так же быстро, как итеративная версия (это называется «оптимизация хвостового вызова»).Например, gcc 4.6.2 удается это сделать - на самом деле, он достаточно умен, чтобы делать и вышеприведенную версию. 

void recursive(int x) {
    if (x >= 10)
        return;
    do_something(x);
    recursive(x + 1);
}
...