Scholieren.com forum - [Prog] C++: recursieve functie

Scholieren.com forum (https://forum.scholieren.com/index.php)

- Software & Hardware (https://forum.scholieren.com/forumdisplay.php?f=20)

- - [Prog] C++: recursieve functie (https://forum.scholieren.com/showthread.php?t=886476)

[C++]recursieve functie

ik heb een recursieve functie waarmee ik wil bepalen of een ingevoerde getal wel of geen priemgetal is. De wiskundige functie die daarbij hoort is de volgende:

a(0) = 4;
a(n+1) = (a(n)²-2) % M(n)

als a(n-2) = 0 dan is n een priemgetal (wel effe in de gaten houden dat de n in de fucntie een andere n is dan de n die je opgeeft om te chekken of het een priem is)

M(n) = 2^n -1.

Dit is mn functie:

Code:

int isPrime(int n, int a, const int Mn)

{

        

        if( a == 0 && (n-1) >= 2)

        {

                a = ((a0*a0) - 2) % Mn;

                isPrime(n-1, a, Mn);

        }

        

        else

        {

                if((n-1) != 1)

                {

                        a = ((a*a)-2) % Mn;

                        isPrime(n-1, a, Mn);

                }



                else

                {

                        if( a == 0 )

                        {

                                return 1;

                        }

                        else

                        {

                                return 0;

                        }

                }

        }

}

nu werkt het op zich wel maar het probleem is, dat ie dan nadat ie bij return 1 of 0 komt eerst n-2 keer weer de if doorloopt om de "geopende" functies te "sluiten".

Nu is dat bij kleine getallen geen probleem, maar als de getallen groter worden krijg je veel overbodig verlies van tijd.

(en ja dit is niet echt een geschikte versie voor grote getallen maar dat komt later)
Iemand tips?

ik snap je functie niet echt, maar naar mijn idee vergeet je de returnwaarde van isPrime af te vangen in je recursive functie.

voorbeeldje uit de losse pols:

Code:

// Faculteit

// Faculteit van 4 is 4 * 3 * 2 * 1 = 24

int faculteit( int n )

{

  int nReturn;

  if( n == 0 ) // Escape value

  {

    nReturn = 1;

  }

  else

  {

    nReturn = faculteit( n - 1 ) * n;

  }



  return nReturn;

}

Welke parameters geef je mee aan je functie? Het lijkt erop dat je globale variabelen gebruikt...

int isPrime(int n, int a, const int Mn)
{
int ret;

if((n-1) > 0)
{
a = ((a*a)-2) % Mn;
ret = isPrime(n-1, a, Mn);
}
else
{
if( a == 0 )
{
ret=ret+4; // jij zegt toch a(0) = 4;
}
}
return ret;
}

a0 wordt niet gedefineerd ??? toch (al staat hij er nu niet meer in)