Primzalenberechnung große zahlen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Primzalenberechnung große zahlen

    Hallo,

    Bei der berechnung von Primzhalen bekomme ich einen Stackoverflow wenn die zahlen zu groß sind (ca. ab 600.000), was kann ich dagegen tun, damit die berechnung für wesentlich größere Zahlen durchgeführt werden kann?

    Quellcode

    1. #include <cmath>
    2. #include <iostream>
    5. #define GROESSE 600000
    7. int eingabe(){
    8. int n;
    9. std::cout << "Feldgröße N: ";
    10. std::cin >> n;
    11. return n;
    12. }
    14. void berechnung(int *feld){
    15. int i;
    16. int j;
    17. //Feldinhalt mit 0 initialisieren
    18. for(i = 0; i <= GROESSE; i++){
    19. feld[i]=1;
    20. }
    21. //i auf erste Primzahl(2) setzen
    22. i=2;
    23. while(i <= GROESSE/2){
    24. while(feld[i]!=1 && i<=GROESSE){
    25. i++;
    26. }
    27. //Vielfaches von i streichen(0)
    28. for(j = 2*i; j <= GROESSE; j += i){
    29. feld[j] = 0;
    30. }
    31. //Suchen nach erst gestrichener Zahl(0)
    32. i++;
    33. }
    34. }
    36. void ausgabe(int *feld){
    37. int i;
    38. for(i = 2; i <= GROESSE; i++){
    39. if(feld[i] == 1){
    40. std::cout << "Primzahl: " << i << "\n";
    41. }
    42. }
    43. }
    46. int main(void){
    48. int n = eingabe();
    51. int feld[GROESSE];
    52. if(feld!=NULL){
    54. berechnung(feld);
    57. ausgabe(feld);
    61. }else{
    62. std::cout << "Es Konnte kein Speicher reserviert werden!!!";
    63. }
    64. std::cout << "Feldgröße N: ";
    65. std::cin >> n;
    66. return 0;
    67. }
    Alles anzeigen


    viele grüße & thx
    bo

  • LOL - ich hab auch sowas gemacht ... Du hast natürlich nen etwas ungünstiges
    Array gewählt, ich geh mal davon aus, Du nimmst diese WegstreichMethode.
    Dann nutze BOOL statt INT ... damit kannste 8-mal soviel speichern
    und theoretisch lässt sich der Code noch optimieren, wenn Du alle
    geraden Zahlen weglässt ;) ... aber das wird dann schonwieder
    schwierig. Hier mein unsauberer Beitrag zum Thema:

    Quellcode

    1. #include <cstdlib>
    2. #include <iostream>
    3. #include <math.h>
    4. using namespace std;
    6. int main(int argc, char *argv[])
    7. {
    8. long int anzahl = 0;
    9. bool const TRUE = 1;
    10. bool const FALSE = 0;
    12. char Frage;
    13. do
    14. {
    15. anzahl = 0;
    16. do
    17. {
    18. cout << "Wieviele Primzahlen sollen es denn sein?: ";
    19. cin >> anzahl;
    20. cout << "\nDann rechne ich ma ...\n";
    21. }
    22. while (anzahl <= 0);
    24. bool *array = new bool[anzahl+1];
    25. bool *gitter = array;
    27. // naja erstmal davon ausgehen, alles sind primzahlen ;-)
    28. for (long int primzahl = 0; primzahl <= anzahl+1; primzahl++)
    29. *(gitter+primzahl)=TRUE;
    31. // dann alle vielfachen der zahlen streichen, wobei ich nur bis zu
    32. // 1/3 ALLER zahlen durchmuss, da ja vielfache von 3 sonst ne ;-)
    33. //ja ziemlich geil geschachtelt, gilt alles als 1 Zeile 8-)
    35. for(long int primzahl = 2; primzahl <= (long double) anzahl/3; primzahl++ )
    36. if ( *(gitter+primzahl) == TRUE )
    37. for(long int getestet = primzahl*2 ; getestet <= anzahl+1; getestet+=primzahl)
    38. if ( getestet <= anzahl+1)
    39. *(gitter+getestet) = FALSE;
    42. // da question
    44. Frage = 0;
    45. do{
    46. cout << "\nmöchten sie das Ergebnis Dezimal, Hexadezimal, Oktal oder Binaer? [D/H/O/B]: ";
    47. cin >> Frage;
    48. }
    49. while (Frage != 'D' & Frage != 'd' & Frage != 'H' & Frage != 'h'
    50. & Frage != 'O' & Frage != 'o' & Frage != 'B' & Frage != 'b');
    52. // und da Ausgabe
    54. cout << "Die Primzahlen lauten: \n";
    55. for(long int primzahl = 0; primzahl <= anzahl ;primzahl++)
    56. if ( *(gitter+primzahl) == TRUE)
    57. switch(Frage)
    58. {
    59. case 'd' : case 'D' :
    60. {
    61. cout << dec << primzahl << "\t";
    62. break;
    63. }
    64. case 'h' : case 'H' :
    65. {
    66. cout << hex << primzahl << "\t";
    67. break;
    68. }
    69. case 'o' : case 'O' :
    70. {
    71. cout << oct << primzahl << "\t";
    72. break;
    73. }
    74. case 'b' : case 'B' :
    75. {
    76. int maxpot = (int) (log((long double) anzahl)/log((long double) 2) + 1 );
    77. long int newprime = primzahl;
    79. for (int j = maxpot; j >= 0; j--)
    80. {
    81. if (newprime - pow(2,j) >= 0)
    82. {
    83. newprime-=(long int) pow(2,j);
    84. cout << "1";
    85. }
    86. else
    87. {
    88. cout << "0";
    89. }
    91. if ( ( (double)( (int) (j/2)) == ((double)j/2)) && j != 0)
    92. cout << ".";
    93. }
    94. cout << "\n";
    96. break;
    97. }
    98. default:
    99. {
    100. cout << "DAS DÜRFTE GARNICHT PASSIEREN - PROGRAMMIERFEHLER !!! " << Frage;
    101. break;
    102. }
    103. }
    105. delete[] array;
    107. // nochma ? nich ? schade.
    109. Frage = 0;
    110. do{
    111. cout << "\n\nnochmal ? [J/N]: ";
    112. cin >> Frage;
    113. }
    114. while (Frage != 'J' & Frage != 'j' & Frage != 'N' & Frage != 'n');
    115. }
    116. while(Frage == 'J' || Frage == 'j') ;
    118. // system("PAUSE");
    119. return EXIT_SUCCESS;
    120. }
    Alles anzeigen


    Kompiliert ohne Fehler bei mia und läuft gut, kann auch mal ne Millionen
    eingeben, ohne dasser abkackt. Problematisch ist nur die Ausgabe, weil
    ich JEDESMAL erst nen Switch/CASE mache, aber ansonsten hätte ich
    die Schleife 4 mal programmieren müssen - naja - Geschmacksfrage.
    Das Array hat an der Stell (Zahl) nur den wert Wahr oder Falsch.
    *wobei ich glaube, dass ich True un False zahlentechnisch verwechselt
    habe, aber macht ja nix - man kanns ja einfach tauschen ?*
    ... ich progge auch noch net so lang 8-P ...

  • Oh hab bei mir noch nen lolligen trivialen Fehler gefunden.
    Da ich die Zahlen nur bis Maximal/3 durchnehme, weil ich
    ja schon weiss, dass 3 ne Primzahl is, ergibts sich bei der
    Eingabe, dass man nur 5 Primzahlen will der Fehler, dasser
    garnich bis zur 3 kommt mitm wegstreichen und daher dann
    komischerweise vergisst die 4 wegzustreichen. Bei 7 gehts
    wieder. Naja - mit so minimalen Werte rechner ja keiner,
    aber zur Not streicht man 4 per Hand weg ;) so vonweg
    if ( max<=5 ) setze *(array+4)=False;
    ... voll die Flicklösung, aber eigentlich interessierts ja keinen.