Primzahl-Sudoku

[holle]

Hallo, ich habe versucht eine Aufgabe zu lösen.

Zitat:

Problem: die Primzahlen
Figur 1 zeigt ein Quadrat, jede Reihe, jede Zeile und die beiden Diagonalen können als fünfstellige Primzahl gelesen werden. Die Reihen werden von links nach rechts gelesen. Die Spalten von oben nach unten. Beide Diagonalen werden von links nach rechts gelesen. Schreibe ein Programm, dass solche Quadrate konstruiert und dazu die Daten in der INPUT.TXT -Datei nutzt.

* Die Primzahlen müssen die gleiche Ziffernsumme haben (Im Beispiel 11)
* Die Zahl in der oberen linken Ecke des Quadrates ist vordefiniert (Im Beispiel 1)
* Eine Primzahl wird eventuell mehr als einmal im Quadrat benutzt
* Falls es mehrere Lösungen gibt, müssen alle dargelegt werden
* Eine fünfstellige Primzahl kann nicht mit Null beginnen, z.B. 00003 ist KEINE fünfstellige Primzahl.

Code:

#include <stdio.h>
#include <stdlib.h>

int quersumme(int number)
{
  int ret = 0;
  int temp = number;
  int i;
  
  for (i = 0; i < 5; i++)
  {
    ret += temp % 10;
    temp /= 10;
  }
  return ret;
}

int main(int argc, char *argv[])
{
  int i, j, k, l, m;
  int summe;
  int erste;
  int anzahl = 0;
  int temp;
  int zahl[100000];
  int lauf[100000];
  int q[5][5];
 
  // eingabe
  printf("SUMME: ");
  scanf("%d", &summe);
  printf("ERSTE ZAHL: ");
  scanf("%d", &erste);
  
  // primzahlen suchen
  for (i = 0; i < 100000; i++)
    zahl[i] = 1;
  for (i = 2; i <= 100000 / 2; i++)
    for (j = 2; j <= 100000 / i; j++)
      zahl[i*j] = 0;
  
  // quersumme
  for (i = 0; i < 100000; i++)
    if (quersumme(i) != summe)
      zahl[i] = 0;

  
  // laufzahlen
  for (i = 10000; i < 100000; i++)
    if (zahl[i] == 1)
    {
      lauf[anzahl] = i;
      printf("> %d\n", i);
      anzahl++;
    }
  printf("anzahl %d\n", anzahl);
  system("pause");
  
  // lösung suchen
  for (i = 0; i < anzahl; i++)
  {
    if ((lauf[i] >= 10000 * erste) && (lauf[i] <= 10000 * erste + 9999))
    {
      q[0][0] = lauf[i] / 10000;
      q[0][1] = (lauf[i] % 10000) / 1000;
      q[0][2] = (lauf[i] % 1000) / 100;
      q[0][3] = (lauf[i] % 100) / 10;
      q[0][4] = lauf[i] % 10; 
      
      if ((q[0][0] != 0) && (q[0][1] != 0) && (q[0][2]) && (q[0][3]) && (q[0][4]))
      {
        for (j = 0; j < anzahl; j++)
        {
          for (k = 0; k < anzahl; k++)
          {
            for (l = 0; l < anzahl; l++)
            {
              for (m = 0; m < anzahl; m++)
              {              
                q[1][0] = lauf[j] / 10000;
                q[1][1] = (lauf[j] % 10000) / 1000;
                q[1][2] = (lauf[j] % 1000) / 100;
                q[1][3] = (lauf[j] % 100) / 10;
                q[1][4] = lauf[j] % 10; 
                
                q[2][0] = lauf[k] / 10000;
                q[2][1] = (lauf[k] % 10000) / 1000;
                q[2][2] = (lauf[k] % 1000) / 100;
                q[2][3] = (lauf[k] % 100) / 10;
                q[2][4] = lauf[k] % 10;
                
                q[3][0] = lauf[l] / 10000;
                q[3][1] = (lauf[l] % 10000) / 1000;
                q[3][2] = (lauf[l] % 1000) / 100;
                q[3][3] = (lauf[l] % 100) / 10;
                q[3][4] = lauf[l] % 10;
                
                q[4][0] = lauf[m] / 10000;
                q[4][1] = (lauf[m] % 10000) / 1000;
                q[4][2] = (lauf[m] % 1000) / 100;
                q[4][3] = (lauf[m] % 100) / 10;
                q[4][4] = lauf[m] % 10;
                
                if (q[0][0] + q[1][0] + q[2][0] + q[3][0] + q[4][0] == summe)
                {
                  if (q[0][1] + q[1][1] + q[2][1] + q[3][1] + q[4][1] == summe)
                  {
                    if (q[0][2] + q[1][2] + q[2][2] + q[3][2] + q[4][2] == summe)
                    {
                      if (q[0][3] + q[1][3] + q[2][3] + q[3][3] + q[4][3] == summe)
                      {
                        if (q[0][4] + q[1][4] + q[2][4] + q[3][4] + q[4][4] == summe)
                        {
                          if (q[0][0] + q[1][1] + q[2][2] + q[3][3] + q[4][4] == summe)
                          {
                            if (q[0][4] + q[1][3] + q[2][2] + q[3][1] + q[4][0] == summe)
                            {
                              temp =  q[0][0] * 10000;
                              temp += q[1][1] * 1000;
                              temp += q[2][2] * 100;
                              temp += q[3][3] * 10;
                              temp += q[4][4]; 
                              
                              if (zahl[temp])
                              {
                                temp =  q[0][4] * 10000;
                                temp += q[1][3] * 1000;
                                temp += q[2][2] * 100;
                                temp += q[3][1] * 10;
                                temp += q[4][0]; 
                                
                                if (zahl[temp])
                                {
                                  temp =  q[0][0] * 10000;
                                  temp += q[1][0] * 1000;
                                  temp += q[2][0] * 100;
                                  temp += q[3][0] * 10;
                                  temp += q[4][0];
                                  
                                  if (zahl[temp])
                                  {
                                    temp =  q[0][1] * 10000;
                                    temp += q[1][1] * 1000;
                                    temp += q[2][1] * 100;
                                    temp += q[3][1] * 10;
                                    temp += q[4][1];
                                    
                                    if (zahl[temp])
                                    {
                                      temp =  q[0][2] * 10000;
                                      temp += q[1][2] * 1000;
                                      temp += q[2][2] * 100;
                                      temp += q[3][2] * 10;
                                      temp += q[4][2];
                                      
                                      if (zahl[temp])
                                      {
                                        temp =  q[0][3] * 10000;
                                        temp += q[1][3] * 1000;
                                        temp += q[2][3] * 100;
                                        temp += q[3][3] * 10;
                                        temp += q[4][3];
                                        
                                        if (zahl[temp])
                                        {
                                          temp =  q[0][4] * 10000;
                                          temp += q[1][4] * 1000;
                                          temp += q[2][4] * 100;
                                          temp += q[3][4] * 10;
                                          temp += q[4][4];
                                          
                                          if (zahl[temp])                     
                                          {
                                            printf("%d%d%d%d%d\n", q[0][0], q[0][1], q[0][2], q[0][3], q[0][4]);
                                            printf("%d%d%d%d%d\n", q[1][0], q[1][1], q[1][2], q[1][3], q[1][4]);
                                            printf("%d%d%d%d%d\n", q[2][0], q[2][1], q[2][2], q[2][3], q[2][4]);
                                            printf("%d%d%d%d%d\n", q[3][0], q[3][1], q[3][2], q[3][3], q[3][4]);
                                            printf("%d%d%d%d%d\n", q[4][0], q[4][1], q[4][2], q[4][3], q[4][4]);
                                            printf("\n");
                                          }
                                        } 
                                      }
                                    }
                                  }
                                }
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }                                       
                                         
  system("PAUSE");   
  return 0;
}

Programmiert werden sollte das ganze in C. Das ganze funktioniert auch soweit sehr gut. Mein Problem ist nur die Laufzeit. Das Programm braucht gut 10-15 Minuten um die Lösung anzuzeigen. Ich habe schon versucht meinen Quelltext zu optimieren, es hat aber nicht viel gebracht. Wisst ihr vielleicht, was ich noch verändern könnte um die Performence zu steigern?

- marcel -

[Florian H]

wenn das in C sein soll, wäre die Frage, wieso du es in die "Object-Pascal / Delphi-Language"-Sparte eines Delphi-Forums setzt .. und nicht in die "Programmieren allgemein"-Sparte eines Delphi-Forums....

Oh.. und ich muss weg, ggf weiterführendere Antworten nachher :>

Grüßle
flo

[new32]

den Teil "primzahlen suchen" kannst du verzürzen, indem du nicht alle i prüfst z.b.4,6,9 weil da können keine neuen nicht-Primzahlen mit erkannt werden.
2*9=6*3