Projekt Euler Aufgabe 11

Stein

Stein

0
Problem 12
08 March 2002

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?
Zum Vergrößern anklicken....
Zu erst habe ich das ganze in Perl versucht:


Code: 
#!/usr/local/bin/perl -w -l
$rekord = 0;
$dieserunde = 0;
for($zahl = 530; $zahl < 539;$zahl++){
$dieserunde = teiler();
if($dieserunde > $rekord){
$rekord= $dieserunde;
print dreieckszahl(), " hat ", $rekord, " Teiler";
}
print $zahl;

}
print $rekord;


sub teiler{
$teileranzahl = 0;
for($j = 1; $j <= dreieckszahl();$j++){
	if(dreieckszahl()%$j == 0) {
		$teileranzahl++;
	}

}
return $teileranzahl;
}

sub dreieckszahl{
$counter = 0;
for($bla = 1; $bla <= $zahl; $bla++){
$counter = $counter +$bla


}
return $counter;
}

Das war aber zulangsam(bei 500 schon pro zahl 20 sec und da hat man gerade mal 48 Teiler) und weil ich erfahren habe, das C++ wesentlich schneller ist:
Code: 
#include <iostream>
#include <ostream>

using namespace std;
static int drzahl(int zahl)
{
	int counter = 0;
	int bla;
	for(bla = 1; bla <= zahl; bla++){
		counter = counter + bla;
	}
	return counter;
}



static int teiler(int zahl)
{
int teileranzahl = 0;
int j;
for(j = 1; j <= drzahl(zahl); j++){
	if(drzahl(zahl)%j == 0){
		teileranzahl++;
	}
}
return teileranzahl;
}


int main() 
{
int rekord = 0;
int dieserunde = 0;
int i;
for(i = 500; rekord < 500;i++){
   dieserunde = teiler(i);
   if(dieserunde > rekord){
      rekord = dieserunde;
      cout << drzahl(i) << " hat " << rekord << " Teiler" << "\n";
      }
   cout << i << "\n";

        
    }
cout << rekord << "\n";

}

Dann war ich 5h weg und sehe das: 2162160 hat 320 Teiler hab ich so umständlich programmiert oder ist die Aufgabe in einer anständigen Zeit nicht lösbar?
 
Wikipedia hat mir folgende Formel geflüstert:
n*(n+1)
2
damit kann ich mir die Funktion
drzahl schonmla sparen. Die teiler funktion könnte man verkürzen indem man nur bist zu wurzel testet und das *2 nimmt, aber bei einer Methode ohne Broute Force bin ich ratlos. Werde mal meine funktionen entsprechen verbessern und dann noch mla testen.
 
Hallo,
deine Methode 'teiler' sieht katastrophal aus.

1. Ich weiß nicht wie der Compiler es handhabt (hängt von Sprache+Compiler ab), aber bei for(j = 1; j <= drzahl(zahl); j++) besteht die gefahr, dass er bei jeder Überprüfung drzahl(zahl) neu berechnet.

2. Deine Methode drzahl() ist sehr ineffektiv.
Du berechnest dort 1+2+3+4+...+zahl, schau dir mal die Summationsformelan.

3. Kann z.B. die Zahl 100 den Teiler 99 haben? Oder 80? Nein, nur maximal 50.
Also statt die Teiler von i=1 bis n zu testen, könnte man die Teiler i=1 bis n/2 testen.Dies lässt sich noch optimieren.
Wenn du weißt, die Zahl 100 ist durch 2 teilbar, ist sie auch durch 50 teilbar.
Kannst also nur bis sqrt(n) laufen (also hier bis 10), und dann die Anzahl der Teiler um 2 erhöhen, sofern du einen Teiler gefunden hast.
Denn wenn p<=sqrt(n) teilt, so hat n auch einen Teiler q mit q>=sqrt(n)
Kannst also einen enormen Faktor einsparen (bei 1 Mio. musst dann nur bis 1000 laufen, Speed-Up um den Faktor 1000)

4. Eine Primfaktorzerlegung von großen Zahlen wird vermutlich deutlich schneller sein, dann von jedem Primfaktor die vielfachen bestimmen, die die Zahl noch teilen.
Etwas aufwendig zu implementieren und eigentlich nicht mehr notwendig.


5. Was ist wohl die kleinste Zahl, mit >5 teilern?
Wenn eine Zahl n Teiler hat, dann heißt das ja, n=pq.
Wenn du also eine Zahl mit 5 Teilern hast, wäre die kleinste mögliche Zahl die mit den Teiler 1,2,3,4,n.
Musst also 3*4=12 betrachten, da jede Zahl die durch 4 teilbar auch durch 2 teilbar ist.
Also kannst du relativ leicht eine untere Schranke für >500 Teiler finden.


Das sind die Ansätze die du hast, wenn du Brute Force befolgen möchtest, sonst kann man die phi-Funktion noch ganz gut nutzen, dazu muss man die Zahl aber wieder in Primzahlen zerlegen.

Edit:
Oder noch besser die Teileranzahlfunktion nutzen, wie BlackSun sie gepostet hat.

Edit 2:
Habs mal in C# implementiert, liefert in knapp 2 Sekunden (auf einem Rechner Anno 2005) das Ergebnis:
Code: 
        static void Main(string[] args)
        {
            DateTime start = DateTime.Now;

            int rekord = 100;
            int tmp = 0;
            long zahl;
            for (int i = 1000; rekord < 500; i++)
            {
                zahl = (i * (i + 1)) / 2;
                tmp = teiler(zahl);

                if (tmp > rekord)
                {
                    rekord = tmp;
                    Console.WriteLine(zahl + " mit " + tmp + " Teilern");
                }           
                
            }

            TimeSpan ende = DateTime.Now - start;

            Console.WriteLine("Dauer: " + ende.TotalSeconds+ " Sekunden");
            Console.ReadKey();

        }

        public static int teiler(long zahl)
        {
            int anzahl = 2;
            long root = (long)Math.Ceiling(Math.Sqrt(zahl));
            for (int i = 2; i < root; i++)
                if (zahl % i == 0)
                    anzahl += 2;

            return anzahl;
        }
 
Code: 
#include <iostream>
#include <ostream>

using namespace std;
static int drzahl(int zahl)
{
	return (zahl * (zahl +1)) / 2;
}



static int teiler(int zahl)
{
int teileranzahl = 0;
int j;
for(j = 1; j*j <= drzahl(zahl); j++){
	if(drzahl(zahl)%j == 0){
		teileranzahl++;
	}
}
return teileranzahl * 2;
}


main() 
{
int rekord = 0;
int dieserunde = 0;
int i;
for(i = 500; rekord < 500;i++){
   dieserunde = teiler(i);
   if(dieserunde > rekord){
      rekord = dieserunde;
      cout << drzahl(i) << " hat " << rekord << " Teiler" << "\n";
      }
   cout << i << "\n";

        
    }
cout << rekord << "\n";

}

und das in ~1 min hätte nie gedachte das das ein dermaßen großer unterschied ist.


Edit:

Habe die letzten beiden Antworten leider erst jetzt gesehen und die Teilerfunktion interessiert mich sehr, da ich Primzhalen berechnen soll und die dafür sehr nützlich währe, aber ich verstehe da nicht viel da ich kein Mathematikstudium habe.

d(n) = r(n), solange d zwischen 1 und n liegt
d(n) ist die teilerfunktio von n, aber was bedeutet:
r(n) und d|n?

gruß waba
 
Hallo,
Original von Stein
und das in ~1 min hätte nie gedachte das das ein dermaßen großer unterschied ist
Zum Vergrößern anklicken....
selbstverständlich.

Du hattest für die 1000. triangle Number eben 1000 Schleifendurchläufe, nun nur noch 1 Addition, 1 Multiplikation und 1 Division.

Bei jedem Schleifendurchlauf hattest du 1 Increment (bla++), 1 Vergleich (bla <= zahl) und 1 Addition (counter += bla) sowie 1 Jump.
Macht also min. 4 Assemblerbefehle pro Durchlauf, also ~4000 Assemblerbefehle zur Berechnung gegen ~3 Assemblerbefehle.
Vorallem die Jumps halten dein Programm extrem auf.

Aber 1 Minute ist immer noch sehr schlecht, siehe mein Edit 2 vom vorherigen post, und das mit C#!
 
Code: 
for(j = 1; j*j <= drzahl(zahl); j++){
Da verlangsamst du es gerade 2x ziemlich stark...
1. Du berechnest immer wieder j * j, du brauchst nur 1x die Wurzel. Bei den 1. Zahlen ist vieleicht j*j schneller, aber sobald es 5, 10 oder 20 werden, wirds langsamer.
2. Du berechnest drzahl(zahl) immer wieder. drzahl(zahl) bleibt aber während der ganzen Funktion konstant, müsste also nur einmal berechnet werden.

Und noch etwas 3. Mach bei dieser Schlaufe immer gleich 2 Schritte auf einmal, das heisst j+= 2 und dann zum Schluss noch testen, ob die Zahl ungerade war, wenn ja das ganze noch einmal durchführen. Dabei spaarst du wenn du die Tips oben schon genutzt hast nochmals ca 1/4 der Zeit. Dabei solltest du auf unter 1 Sekunde kommen.
 
könntest du mir vielleich diese Zeile mal erklären? Das ist die einzige wo ich garnicht durchblick:
Code: 
long root = (long)Math.Ceiling(Math.Sqrt(zahl))
 
Original von Stein
könntest du mir vielleich diese Zeile mal erklären? Das ist die einzige wo ich garnicht durchblick:
Code: 
long root = (long)Math.Ceiling(Math.Sqrt(zahl))
Zum Vergrößern anklicken....

Die Zeile berechnet die zur größeren Zahl hin gerundete Wurzel.

Wobei in Elderans Code noch ein kleinerer Fehler drin ist, da etwa der Teiler 6 von 36 doppelt gezählt würde, was in diesem Fall aber nicht schlimm ist.
Tipp: Viele gute Lösungansätze teils in <1s findest du auch im Lösungsthread zu Problem 12 auf projecteuler.net.
 
www.projecteuler.net

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
Zum Vergrößern anklicken....
 
Erstmla vielen dank und dann das Programm mit dem ich ~5sec brauche(pc auhc etwas älter). Bis ich erstmal drauf gekommen bin wielange so eine Ausgabe dauert.......
#include <iostream>
#include <ostream>
#include <cmath>

using namespace std;
static int drzahl(int zahl)
{
return (zahl * (zahl +1)) / 2;
}



static int teiler(int zahl)
{
int teileranzahl = 0;
int j;
double abc = ( (zahl * (zahl +1)) / 2);
int lager = static_cast<float>(sqrt(abc)) + 1;
int lagerzwei = (zahl * (zahl +1)) / 2;
for(j = 1; j <= lager; j++ ){
if(lagerzwei%j == 0){
teileranzahl+= 2;
}
}
return teileranzahl ;
}


main()
{
int rekord = 0;
int dieserunde = 0;
int i;
int siegerzahl = 0;
for(i = 1000; rekord < 500;i++){
dieserunde = teiler(i);
if(dieserunde > rekord){
rekord = dieserunde;
siegerzahl = i;
// cout << drzahl(i) << " hat " << rekord << " Teiler" << "\n";
}
//cout << i << "\n";


}
cout << rekord << " " << siegerzahl <<"\n";

}
Zum Vergrößern anklicken....
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben