Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
20.07.2002, 14:55 Uhr
virtual
Sexiest Bit alive
(Operator)

Das 2. Sonntagsrätsel (bereits heute, weil ich morgen nicht da bin!)
Okay, wir gehen in die zweite Runde. Diesmal gibt es zwei Rätsel, ein leichtes, ein weniger leichtes.

Die etwas leichtere Aufgabe
Primzahlzwillinge sind die Zahlenpaare, die als Differenz 2 haben und beide Primzahlen sind. Zu entwickeln ist ein Programm, daß alle Primzahlzwillinge in einem Zahlenbereich findet, den der Benutzer interaktiv festlegen kann. Gewonnen hat die Lösung, welche am schnellsten alle Primzahlzwillinge zwischen 2000000 und 3000000 findet.
Ich beantworte Fragen bzgl. Aufgabenstellung und Herangehensweise gerne.

Die weniger leichte Aufgabe (Buchstabenwürmer)
Zu entwickeln ist ein Ver- und Entschlüsselungsprogramm der etwas anderen Art

:
Das Programm erwartet als Parameter den Namen einer Datei und ersetzt diese wie folgt durch eine verschlüsselte Version:
Beim Verschlüsseln werden jeweils 64 Bit der als binäre geöffneten Datei als eine positive ganze Zahl interpretiert und das korrespondierende Zahlwort + Newline als Verschlüsselungstext ersetzt (Sollten am Ende der Datei keine 64 Bit zusammenkommen, werden halt nur die Restbits verwendet).
Einige einfache Zahlen mal zur Veranschaulichung

Code:

0x0000000000000000 => "null\n"
0x0000000000000010 => "sechzehn\n"
0x1234567812345678 => "einetrillionendreihundertelfbilliardensiebenhundertachtundsechzigbillionenvierhunderfünfundsechzigmilliardenhundertdreiundsiebzigmillionenhunderteinundvirzigtausendhundertzwölf"

(ohne Gewähr, hab das Programm noch nicht geschrieben).
Außerdem soll das Programm eine Option besitzen, die es erlaubt die Verschlüsselung rückgängig zu machen (das scheint mir der nicht triviale teil zu sein). Gewonnen hat die Lösung, die es am schnellsten schafft, eine 2MB Datei nach obigen Regeln zu ver- und wieder entschlüsseln.
Gefordert ist weiterhin, daß das Programm in reinem ANSI C bzw. C++ geschrieben ist. (Achtung: der Datentyp "long long" ist zwar ANSI C, aber nicht ANSI C++!)
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
20.07.2002, 21:09 Uhr
~NemoEimi
Gast

Ok, hier mal eine Lösung für die einfachere Aufgabe:

C++:

#include <stdio.h>
#include <cstdlib>

unsigned int smallprimes[100000], quadrate[100000];

bool prime_p(unsigned int n) {
  for (unsigned int i = 1; quadrate[ i ] <= n; i++)
    if (n%smallprimes[ i ]==0) return(0);
  return(1);
  }

unsigned int naechste_primzahl(unsigned int n) {
  unsigned int k = n + 2;
  while (!prime_p(k)) {
    k = k + 2;
    }
  return(k);
  }

void erzeuge_erste_primzahlen(unsigned int n) {
  unsigned int z = 2;
  for (unsigned int i = 5; i <= n; i = naechste_primzahl(i)) {
    smallprimes[z] = i; quadrate[z] = i*i; z = z + 1;
    }
  }

inline bool twin_test(unsigned int n) {
  unsigned int m = n + 2;
  for (register unsigned int i = 1; quadrate[ i ] <= m; i++) {
    if (n%smallprimes[ i ]==0) return(0);
    if (m%smallprimes[ i ]==0) return(0);
    }
  return(1);
  }

int main(unsigned int argc, char *argv[]) {
  smallprimes[1] = 3; quadrate[1] = 9;
  erzeuge_erste_primzahlen(100000);
  unsigned int a = atoi(argv[1]); unsigned int b = atoi(argv[2]);
  a = a - a%6 + 5;
  for (unsigned int i = a; i <= b; i=i+6)
    if (twin_test(i)) printf("%d\n",i);
  return(0);
  }

Grüße,
NemoEimi

Dieser Post wurde am 23.07.2002 um 12:51 Uhr von FloSoft editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
21.07.2002, 16:49 Uhr
Bruder Leif
dances with systems
(Operator)

Moin!

Nicht ganz so schnell, aber (zumindest für mich) einfacher:

C++:

#include <iostream>

using namespace std;

//##############################################################################

const int cMaxPrimCount = 1000000;  // Maximal 1 Mio. Primzahlen, entsprechend 4 MB

// Die ermittelten Primzahlen
unsigned int iPrim[cMaxPrimCount], iPrimCount=1;

// Quadrate der ermittelten Primzahlen
unsigned int iPrimQuadrate[cMaxPrimCount];

//##############################################################################

int main()
{
   int iIsPrim=1;
   unsigned int iZwillingStart, iZwillingStop;

   if(sizeof(unsigned int) < 4)
   {
      cout << "Der Typ unsigned int muss mindestens 4 Byte umfassen!" << endl;
      return 1;
   }

   iPrim[0]=2;
   iPrimQuadrate[0]=4;

   cout << "Primzahlenzwillinge suchen" << endl << "Untergrenze: " << flush;
   cin >> iZwillingStart;
   cout << "Obergrenze : " << flush;
   cin >> iZwillingStop;

   if(iZwillingStart > iZwillingStop || iZwillingStop > 5000000)
   {
      // Weiß nicht, wie viele Primzahlen in ein 1Mio-Array passen...
      // So klappts auf jeden Fall!
      cout << "Sorry, das ist mir zu hoch" << endl;
      return 1;
   }

   cout << endl << "Primzahlen bis " << iZwillingStop << " werden ermittelt..." << endl;

   // Primzahlen ermitteln
   for(register unsigned int l=3; ; l+=2)
   {
      // Wir prüfen die Teilbarkeit mit schon ermittelten Primzahlen
      for(register int j=0; iPrimQuadrate[j]<=l; j++)
      {
         if(!(l % iPrim[j]))
         {
            iIsPrim = 0;
            break;
         }
      }

      if(iIsPrim)
      {
         // Primzahl gefunden! Ins Array eintragen!
         iPrim[iPrimCount] = l;
         iPrimQuadrate[iPrimCount] = l*l;
         iPrimCount++;

         if(l >= iZwillingStop) break;
      }
      else
         iIsPrim = 1;
   }

   // An diesem Punkt wurden iPrimCount Primzahlen bis max. iZwillingStop ermittelt.
   // Jetzt durchsuchen wir das Array nach Zwillingen!
   // Geht zwar noch etwas schneller im 1-Pass-Verfahren, aber so isset verständlicher ;-)

   cout << iPrimCount << " Zahlen, groesste:" << iPrim[iPrimCount-1] << endl;
   cout << "Zwillinge werden gesucht..." << endl;
   for(unsigned int l=0; l<iPrimCount; l++)
   {
      if(iPrim[l] >= iZwillingStart)
      {
         // Ab hier nach Zwillingen suchen
         for(; iPrim[l+1] <= iZwillingStop; l++)
         {
            if(iPrim[l]+2 == iPrim[l+1])  // gefunden!
               cout << iPrim[l] << ", " << iPrim[l+1] << endl;
         }

         break;
      }
   }
   return 0;
}

--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
21.07.2002, 18:51 Uhr
~guzi
Gast

Hallo,
hier meine Lösung. Lässt sich bestimmt noch weiter optimieren.

C++:

#include <iostream.h>

void prim(int von, int bis)
{
    int* a= new int[bis+1];
    //a[1] = 0;

    //initialisieren
    for (int m=2; m<=bis; m++)
        a[m] = 1;

    //alle vielfachen heraussieben
    for (int i=2; i*i <= bis; i++)
        if (a[ i ])
            for (int j = i*i; j<=bis;  j += i)
                a[j] = 0;

    for ( ; von<=bis; von++)
        if (a[von] && a[von+2])
            cout << von << "  " << von+2 << endl;

    delete [] a;
}

main()
{
    prim(2000000 ,3000000);
    return 0;
};

[i]editiert: Habe mir mal gewagt [ i ] abzuändern. Bei Cut&Paste also Vorsicht 20:48 Uwe[i]

Dieser Post wurde am 21.07.2002 um 20:48 Uhr von Uwe editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
21.07.2002, 19:05 Uhr
~guzi
Gast

if (a[i])
...muss es selbstverständlich heissen.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
21.07.2002, 19:07 Uhr
~guzi
Gast

if (a[ hier steht das i ] )

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
23.07.2002, 12:24 Uhr
virtual
Sexiest Bit alive
(Operator)

@NemoEimi
Tja, schnell is dein Program zwar, aber es ist nicht ganz bugfrei. Mathematisch gesprochen: es findet leider nur eine echte Teilmenge der gesuchten Zahlen. Willst Du einen Tip?

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Dieser Post wurde am 23.07.2002 um 12:25 Uhr von virtual editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
23.07.2002, 13:04 Uhr
~NemoEimi
Gast

[quote]virtual postete
@NemoEimi
Tja, schnell is dein Program zwar, aber es ist nicht ganz bugfrei. Mathematisch gesprochen: es findet leider nur eine echte Teilmenge der gesuchten Zahlen.

Mein Programm findet natürlich keine Zwillinge, bei denen der kleinere Partner durch drei teilbar ist *g*. Das stört mich nur wenig, denn von denen gibt es nur endlich viele

)), und leicht zu beheben ist dieses Problem auch.
Ansonsten findet es 6061 Primzahlzwillingspaare zwischen 2000000 und 3000000, genauso wie beispielsweise das Programm von Leif oder wie dieses garantiert bugfreie ;-) Aribas-Programm:

function extremely_stupid_twin_counter(a,b)
var
i, z: integer;
begin
z := 0;
for i := a to b do
if (prime32test(i) and prime32test(i+2)) then z := z + 1; end;
end;
return(z);
end;

Grüße,
NemoEimi

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
23.07.2002, 15:25 Uhr
virtual
Sexiest Bit alive
(Operator)

Übrigens:

C++:

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

unsigned long Primzahlen[65535] = {3, 5, 7};
unsigned long Quadrate[65535] = {9, 25, 49};
unsigned Anzahl = 3;

/*  n sei die Mittelzahl vom pot. Zwilling, also
    durch 6 teilbar. Der Spezialfall n == 4 wird
    hier nicht berücksichtigt. */
int
istZwilling(
    unsigned long n)
{
    unsigned j;
    unsigned k;
    unsigned long n1 = n-1;
    unsigned long n2 = n+1;
    unsigned long p;

    /* Prüfe auf Primzahlzwilling mit den bereits
       ermittelten Testprimzahlen */
    for(j=0; Quadrate[j]<=n2 && j<Anzahl; ++j)
        if (n1%Primzahlen[j]==0 || n2%Primzahlen[j]==0)
            return 0;
    if (j<Anzahl) return 1;

    /* Es sind nicht genug Testprimzahlen da -
       wir muessen weitere finden, machen aber
       gleichzeitig die notwendigen tests */
    for(p=Primzahlen[Anzahl-1]+2; ; p+=2)
    {
        for(j=0; Quadrate[j]<=p; ++j)
            if (p%Primzahlen[j]==0)
                break;
        if (Quadrate[j]>p)
        {
            Primzahlen[Anzahl] = p;
            Quadrate[Anzahl] = p*p;
            j = Anzahl++;
            if (n1%Primzahlen[j]==0 || n2%Primzahlen[j]==0)
                return 0;
            if (Quadrate[j]>n2)
                return 1;
        }
    }
}

int
main(
    int argc,
    char** argv)
{
    unsigned long von = atol(argv[1]);
    unsigned long bis = atol(argv[2]);

    if (von<4 && bis>4)
        printf("3, 5\n");
    von -= von%6;
    if (von<6) von = 6;
    while (von<bis)
    {
        if (istZwilling(von)) printf("%lu, %lu\n", von-1, von+1);
        von += 6;
    }
}

Läuft - mindestens hier auf der Linuxkiste hier - in 0.25 Sekunden durch.
Deines braucht 0.28 Sekunden, also 12% mehr. Hab noch nicht genau geguckt, wo da der Unterschied ist. (Bei den zahlen 0-10000000 ist der Unterschied mit 4.5% deutlich geringer...)
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
23.07.2002, 18:30 Uhr
~NemoEimi
Gast

Auf meiner Linuxkiste ist das hier:

C++:

#include <stdio.h>
#include <cstdlib>

unsigned int smallprimes[65535], quadrate[65535];

bool prime_p(unsigned int n) {
  for (unsigned int i = 1; quadrate[i] <= n; i++)
    if (n%smallprimes[i]==0) return(0);
  return(1);
  }

unsigned int isqrt(unsigned int n) {
  unsigned int a = n, b = n-1;
  while (b < a) {
    a = b; b = a + n/a >> 1;
    }
  return(b);
  }

unsigned int naechste_primzahl(unsigned int n) {
  unsigned int k = n + 2;
  while (!prime_p(k)) {
    k = k + 2;
    }
  return(k);
  }

void erzeuge_erste_primzahlen(unsigned int n) {
  unsigned int z = 2;
  for (unsigned int i = 5; i <= n; i = naechste_primzahl(i)) {
    smallprimes[z] = i; quadrate[z] = i*i; z = z + 1;
    }
  }

inline bool twin_test(unsigned int n) {
  unsigned int m = n + 2;
  for (register unsigned int i = 1; quadrate[i] <= m; i++) {
    if (n%smallprimes[i]==0) return(0);
    if (m%smallprimes[i]==0) return(0);
    }
  return(1);
  }

int main(unsigned int argc, char *argv[]) {
  smallprimes[1] = 3; quadrate[1] = 9;
  unsigned int a = atoi(argv[1]); unsigned int b = atoi(argv[2]);
  erzeuge_erste_primzahlen(isqrt(b)+1);
  a = a - a%6 + 5;
  for (unsigned int i = a; i <= b; i=i+6)
    if (twin_test(i)) printf("%d\n",i);
  return(0);
  }

nochmal knapp 20 Prozent schneller als Dein Code

.

Grüße,
NemoEimi

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: