[C++] Priemgetallen van JAVA naar C++

[Priet]

Ik had op GoT een prachtig stukje Java-code gevonden waarmee je priemgetallen kunt berekenen en op het scherm kunt tonen:

Java:

public class Priem
{
    public static void main(String[] ps)
    {
        int MAX = 100;
        final int MAXHALF = (MAX - 1)/2;
        boolean[] numbers = new boolean[MAXHALF];
        int i, j, a;
        double l;

        long millis = System.currentTimeMillis();

        l = (Math.sqrt(MAX) - 1.0) / 2.0;
        for(i= 1; i <= l; ++i) {
          if(!numbers[i]) {
            a= i * 2 + 1;
            for(j= i + a; j < MAXHALF; j+= a) {
            if(!numbers[j]) numbers[j]= true;
            }
          }
        }

        System.out.println("Miliseconds: " +
            (System.currentTimeMillis() - millis));

        System.out.print("2 ");
        for(j= 0, i= 1; i < MAXHALF; ++i) {
          if (!numbers[i]) {
            if (j++<20) System.out.print((i * 2 + 1) + " ");
          }
        }

        System.out.println("\nTotaal: " + j);
        System.out.println(MAXHALF);
        System.out.println(l);
    }
}

Dit heb ik nodig voor een programmaatje dat ik in C++ maak dat ook priemgetallen moet kunnen vinden. Ik heb de code omgezet naar C++ maar dan doet 'ie het opeens niet meer

C++:

#include <iostream>
#include <limits>
#include <cmath>

using namespace std;   

int main(int argc, char *argv[])
{
  // Selecteer priemgetallen
  int MAX = 100;
  const int MAXHALF = (MAX - 1)/2;
  bool numbers[MAXHALF];
  int i, j, a;
  double l;

  l = (sqrt((double) MAX) - 1.0) / 2.0;
  for(i= 1; i <= l; ++i) 
  {
    if(!numbers[i]) 
    {
      a= i * 2 + 1;
      for(j= i + a; j < MAXHALF; j+= a) 
        if(!numbers[j]) numbers[j]= true;
    }
  }

  cout << "2 ";
  for(j= 0, i= 1; i < MAXHALF; ++i) 
  {
    if (!numbers[i]) 
    {
        j++;
        cout << (i * 2 + 1) << " ";
    }
  }
  
  cout << endl << "Totaal: " << j << endl;
  cout << "MAXHALF: " << MAXHALF << endl;
  cout << "l: " << l << endl;
  system("PAUSE");  
  return 0;
}

Voor zover ik kan zien zien beide codes identiek aan elkaar Maar op de een of andere manier vind de C++ variant maar 11 ipv 25 priemgetallen t/m de 100...

Wie ziet wat ik fout doe

[ Voor 8% gewijzigd door Priet op 19-05-2003 00:02 . Reden: code-tag ]

[Soultaker]

Het enige dat ik zag, is dat je vergeet je 'numbers' array te initialiseren. Je zult in C++ alle elementen op 'false' moeten initialiseren (met memset of een simpel for-lusje); in Java gebeurt dit automatisch voor je.

Overigens heb je een vrij vieze implementatie van dit algoritme te pakken (die wortelberekening alleen al). Misschien doe je er verstandig aan nog wat verder hier op GoT te zoeken, want ik weet vrij zeker dat er veel nettere, duidelijkere en betere implementaties langsgekomen zijn, ook wel in C/C++, denk ik. Je kunt ook op Google zoeken naar de zeef van Erastothenes (sieve of Erastothenes), zoals dit algoritme heet.

[ Voor 3% gewijzigd door Soultaker op 18-05-2003 16:53 ]

[Priet]

Ah op die fiets Ik ga eens even verder zoeken, mijn dank is groot!

[Priet]

Als ik nog even mag?

code:

for(i= 1; i <= l; ++i) 
  {
    if(!numbers[i]) 
    {
      a= i * 2 + 1;
      for(j= i + a; j < MAXHALF; j+= a) 
        if(!numbers[j]) numbers[j]= true;
    }
}

Dit is toch al een implementatie van de zeef van Erastodinges?

[ Voor 3% gewijzigd door Priet op 18-05-2003 17:32 ]

[Priet]

Voor de naslag en voor iedereen die hier later nog naar mocht op zoek mocht zijn zal ik mijn oplossing hier posten. Er zullen vast nog wel wat bugs inzitten, maar ik ben nog niet zo ervaren met C++ dat ik die er allemaal snel uit kan vissen.

C++:

bool isPriem(int getal)
{
  bool debug = false;
  bool printprimes = false;
  bool gevonden = false;
  
  // Selecteer priemgetallen adhv 'de zeef van Erathostenos'
  const int MAX = 1000;
  bool zeef[MAX];
  for (int zeefindex = 0; zeefindex < MAX; zeefindex++)
    zeef[zeefindex] = true;
  zeef[0] = false; zeef[1] = false;
  
  for (int i = 2; i < MAX; i++)
  {
   if (debug) cout << "Nieuwe index: " << i << endl;
   if (zeef[i])
     for (int j = i * 2; j < MAX; j+=i)
     {
       if (debug) cout << "  @: " << i << " " << j << endl;
       zeef[j]=false;
     }
  }

  // Controleer of getal nog in de zeef zit
  int aantal=0;
  for (int zeefindex2 = 0; zeefindex2 < MAX; zeefindex2++)
  {
    if (zeef[zeefindex2]) 
    {
      aantal++;
      if (debug) cout << zeefindex2 << "->" << zeef[zeefindex2] << " | ";
      if (printprimes) cout << zeefindex2 << " ";
    }
    if (zeef[zeefindex2] && zeefindex2 == getal)
    {
      gevonden = true;
      if (!printprimes) break;
    }
  }
  if (debug) cout << "Totaal aantal gevonden priemgetallen: " << aantal << endl;
  return gevonden;
}

Met bovenstaande code kun je alle priemgetallen tot 1000 opzoeken en je kunt een controleren of een getal een priemgetal is.

[ Voor 22% gewijzigd door Priet op 18-05-2003 23:59 . Reden: code-tag ]

[.oisyn]

Tip: gebruik voortaan [norml]

C++:

...

en

Java:

...

[/] voor syntax highlighting en regelnummering

[Soultaker]

Leuk om te horen dat het je zelf nog gelukt is. Begrijp je nu ook hoe het algoritme werkt (is niet zo ingewikkeld, maar wel interessant)?

Je gebruikt het algoritme trouwens op een erg onhandige manier. Het is namelijk bedoeld om alle priemgetallen tot een bepaald maximum te vinden (bijvoorbeeld, alle priemgetallen kleiner dan 1000). Als je simpelweg wilt controleren of een bepaald getal een priemgetal is, kun je veel beter kijken of je een getal kunt vinden waardoor je het kunt delen (want dan is het dus geen priemgetal).

Dat zou dan zoiets worden:

C++:

bool isPrime(int n)
{
    for(int m = 2; m * m <= n; ++m)
        if((n % m) == 0)
            return false;
    return true;
}

(Merk op dat je dit algoritme op een aantal manieren kunt verbeteren; een simpele en effectieve verbetering is om eenmaal te testen op deling door 2 en vervolgens in de for lus m te laten beginnen op 3 en met 2 op te hogen, aangezien een getal dat niet deelbaar is door 2 ook niet deelbaar is door 4, 6, 8, enzovoorts.)

Jouw implementatie werkt ook wel, maar nu genereer je altijd alle priemgetallen tot 1000 alleen maar om vast te stellen of daar 1 bepaald getal tussen zit. Sowieso zou je je maximum beter gelijk kunnen stellen aan het te testen getal, dan genereer je in ieder geval precies genoeg priemgetallen.

[ Voor 14% gewijzigd door Soultaker op 18-05-2003 22:33 ]

[crisp]

Soultaker schreef op 18 mei 2003 @ 22:30:
Leuk om te horen dat het je zelf nog gelukt is. Begrijp je nu ook hoe het algoritme werkt (is niet zo ingewikkeld, maar wel interessant)?

Je gebruikt het algoritme trouwens op een erg onhandige manier. Het is namelijk bedoeld om alle priemgetallen tot een bepaald maximum te vinden (bijvoorbeeld, alle priemgetallen kleiner dan 1000). Als je simpelweg wilt controleren of een bepaald getal een priemgetal is, kun je veel beter kijken of je een getal kunt vinden waardoor je het kunt delen (want dan is het dus geen priemgetal).
[...]

het is voldoende om te testen of dat getal deelbaar is door een priemgetal tot aan sqrt(je_getal); hiervoor heb je echter wel een lijstje priemgetallen nodig

[MSalters]

Soultaker schreef op 18 May 2003 @ 16:53:
Het enige dat ik zag, is dat je vergeet je 'numbers' array te initialiseren. Je zult in C++ alle elementen op 'false' moeten initialiseren (met memset of een simpel for-lusje); in Java gebeurt dit automatisch voor je.

In C++ ook, alleen niet in C - en dit is een C array. De C++ variant,
std::vector<bool> naam ( grootte ) wordt keurig op false geinitialiseerd.

[Soultaker]

MSalters schreef op 19 May 2003 @ 00:07:
[...]

In C++ ook, alleen niet in C - en dit is een C array. De C++ variant,
std::vector<bool> naam ( grootte ) wordt keurig op false geinitialiseerd.

Praat alsjeblieft niet zulke onzin: een array is een array en een vector is een vector. Als een vector een array was, dan hadden ze 'm wel array genoemd, denk je niet?

In C++ worden arrays net zoals in C geinitialiseerd. Sinds kort weet ik trouwens ook dat dat misschien nog wel het mooiste zo kan:

code:

   bool numbers[MAX] = {};

Maar goed, feit blijft dus dat het een array is, niets anders, en zeker geen vector.

[Soultaker]

crisp schreef op 18 May 2003 @ 23:34:
het is voldoende om te testen of dat getal deelbaar is door een priemgetal tot aan sqrt(je_getal); hiervoor heb je echter wel een lijstje priemgetallen nodig

Die optimalisatie pas ik ook toe, hoor, alleen interesseren al die tussenliggende priemgetallen me niets, als ik ze toch weer weggooi.

[crisp]

Soultaker schreef op 19 May 2003 @ 02:32:
[...]

Die optimalisatie pas ik ook toe, hoor, alleen interesseren al die tussenliggende priemgetallen me niets, als ik ze toch weer weggooi.

sla dan op z'n minst, nadat je deelbaarheid door 2 hebt getest, de even getallen over; scheelt je de helft... lezen is moeilijk op maandag ochtend
ja, gebruik maken van een lijst priemgetallen is alleen effectief als je een hele reeks priemgetallen wilt vinden (dan sla je ze toch op); voor het testen van een enkel priemgetal is het waarschijnlijk minder efficient.

[ Voor 29% gewijzigd door crisp op 19-05-2003 08:54 ]

[Priet]

Soultaker, wederom bedankt. Is behoorlijk wat minder code, maar 't kost wel ff tijd om te begrijpen wat 'ie nu precies doet.

[MSalters]

Soultaker schreef op 19 May 2003 @ 02:30:
[...]
Praat alsjeblieft niet zulke onzin: een array is een array en een vector is een vector. Als een vector een array was, dan hadden ze 'm wel array genoemd, denk je niet?

Nee, eigenlijk, en met een goede reden: Dat zou teveel verwarring opleveren (is wel overwogen). Het nadeel nu is dat mensen de arrays uit C gebruiken op grond van hun naam, waar std::vector beter/handiger/simpeler is.


In de wiskunde wordt Array typisch gebruikt voor een reeks met variabele grootte, terwijl een Vector typich een vaste grootte heeft. Voorbeeld: 2D vector. In C++ is dat dus precies andersom, dat geeft maar aan dat de keuze voor de naam std::vector niet echt handig was, maar een afweging van twee kwaden.

Daar komt dan nog eens bovenop dat een std::vector ook als een echte C array geimplementeerd is: &front() wijst naar dat adres.