Wettbewerb: Primfaktorzerlegung

Hi,

wir wärs mal wiedermal mit nem kleinen Wettbewerb

Aufgabe: Zerlege eine endliche Menge von Zahlen in ihre Primfaktoren.

Gewinner ist natürlich derjenige, mit dem schnellsten Algorithmus. Eigentlich will ich ja auch nur sehen, wie schnell Volkard ist.

Weiteres: Welche obere Zahlengrenze nehmen wir ? Wo testen wir ? Wie testen wir ? ... ?
Einsendeschluss: in einer Woche, Punkt 23:59.

Besteht Interesse ?

knivil

War schon mal Thema: http://www.c-plusplus.net/forum/viewtopic-var-t-is-253651-and-start-is-0-and-postdays-is-0-and-postorder-is-asc-and-highlight-is-.html

Einsendeschluss: in einer Woche, Punkt 23:59.

Zu kurzfristig, man moechte sich vielleicht auch mal in die aktuelle Literatur einlesen. Zahlen kleiner als 10^60 sind ungeeignet.

Eigentlich will ich ja auch nur sehen, wie schnell Volkard ist.

Tja, aber volkard hat sich vielleicht schon etwas intensiver mit dem Thema beschaeftigt.

wenn die Zahlengrenze < 10^100 ist, würd ich da nicht mitmachen.

knivil

juudff schrieb:

wenn die Zahlengrenze < 10^100 ist, würd ich da nicht mitmachen.

Und warum, es soll ja auch nicht Monate dauern.

KasF schrieb:

Aufgabe: Zerlege eine endliche Menge von Zahlen in ihre Primfaktoren.

es reicht doch eine zahl, zusammengesetzt aus 2 grossen primzahlen, wofür ein testprogramm sich 'nen wolf rechnet, z.b. eine stunde braucht oder so. gewonnen hat das programm, das die primfaktoren am schnellsten findet.

SeppJ

Interessant fände ich so einen Wettbewerb schon, aber das Thema Primfaktorzerlegung ist einfach zu ausgelutscht. In einer für einen Programmierwettbewerb angemessenen Zeit würde das wahrscheinlich bloß darauf hinauslaufen, dass es am effizientesten ist, wenn man sich den neuesten Quellcode aus einer wissenschaftlichen Veröffentlichung schnappt.

Denk dir etwas ganz neues als Aufgabe aus, wozu es noch nichts gibt, so dass man sich eigene Algorithmen ausdenken muss.

otze

Dito. Primfaktorzerlegung wird überall durchgekaut. Und es ist schlichtweg langweilig. Es gibt eh keinen wirklich guten Algorithmus als die paar Standarddinger und dann ist der ganze Wettbewerb nur Taktschubsen.

Wie wärs mit nem Wettbewerb aus dem Bereich Objekterkennung/Klassifikation? da gibts noch ne Menge unbeackertes Gebiet. Oder: ne KI zu einem (Brett-)spiel schreiben. Und am Ende treten einfach mal alle gegeneinander an und die beste Ki gewinnt.

SeppJ

otze schrieb:

Wie wärs mit nem Wettbewerb aus dem Bereich Objekterkennung/Klassifikation? da gibts noch ne Menge unbeackertes Gebiet. Oder: ne KI zu einem (Brett-)spiel schreiben. Und am Ende treten einfach mal alle gegeneinander an und die beste Ki gewinnt.

Das finde ich gut. Da kann man sich auch schnell was ausdenken, was noch keiner gemacht hat, indem man ein bekanntes Brettspiel variiert. Zum Beispiel 5-gewinnt, statt 4-gewinnt. Interessant wäre vielleicht auch ein Spiel mit Zufallselementen, zum Beispiel eine Monopoly-KI.

otze schrieb:

Wie wärs mit nem Wettbewerb aus dem Bereich Objekterkennung/Klassifikation? da gibts noch ne Menge unbeackertes Gebiet. Oder: ne KI zu einem (Brett-)spiel schreiben. Und am Ende treten einfach mal alle gegeneinander an und die beste Ki gewinnt.

Ich bin dafür, aber nur unter einer Bedinung.
Alle fertigen Einsendungen gehen an meine E-Mail Adresse.
Ausgewertet und bekannt gegeben wird dann 2 Wochen später.

Ich such mir dann in der Zwischenzeit den besten Algorithmus raus und melde ihn in den USA zum Patent an.

rapso

vielleicht mal primfaktorzerlegung von einer zahl auf n-cores. ich glaube das ist noch nicht zu sehr "ausgelutscht".

rapso schrieb:

vielleicht mal primfaktorzerlegung von einer zahl auf n-cores. ich glaube das ist noch nicht zu sehr "ausgelutscht".

ist bestimmt auch ausgelutscht. irgendwelche RSA-crackversuche laufen sicherlich nicht nur auf einzelnen CPUs. oder gleich mit sowas anfangen: http://eref.uqu.edu.sa/files/Others/Elliptic Curves/Parallel Sieving Implementation for Number Factoring.pdf

SeppJ schrieb:

Interessant fände ich so einen Wettbewerb schon, aber das Thema Primfaktorzerlegung ist einfach zu ausgelutscht. In einer für einen Programmierwettbewerb angemessenen Zeit würde das wahrscheinlich bloß darauf hinauslaufen, dass es am effizientesten ist, wenn man sich den neuesten Quellcode aus einer wissenschaftlichen Veröffentlichung schnappt.

Das habe ich mir damals auch gedacht, war aber zu faul mir was anderes einfallen zu lassen. Früher hatten wir hier immer ein paar ganz interessante Wettbewerbe (Jester war glaub ich der Initiator).

SeppJ schrieb:

Denk dir etwas ganz neues als Aufgabe aus, wozu es noch nichts gibt, so dass man sich eigene Algorithmen ausdenken muss.

Bei Zeit und Gelegenheit werde ich mir mal was bis Sonntag einfallen lassen. Andere Vorschläge sind natürlich auch willkommen

Folgendes:

Es wird eine kleine 2D-Map geben mit willkürlich verteilten Sitzen.

Es werden anzahlSitze-1 Trolle in der Map rumtrollen.
Ne Zeit oder Musik wird laufen.
Bei Zeit-/Musikstop müssen die Trolle sich sofort einen Sitzplatz suchen.
Trolle müssen immer in Bewegung bleiben.
...

Die Trolle werden folgende Informationen erhalten:

Signal Zeit-/Musikstop
Position Sitze und other Trolls
...

Ziel ist es natürlich den Trollbewegungsalgorithmus zu implementieren.

... weitere Ideen oder Anmerkungen dazu ?

otze

Ja, gibts Kriterien bezüglicher der Qualität des Algorithmus?

schafft die zahl 50000000 in unter 2 minuten

int c=0;
int zr=50;
for(int i=zr;i>0;i--)
{
c=0;
for(int z=1;z<=zr;z++){
if(i%z==0){ // wenn i durch z rest 0 ist könnte es eine primzahl sein
c++;

}
if (c<2){
break;
}
if(c<=2&&z==i){
// wenn die zahl nur 2 mal teilbar ist, wo rest 0 ergibt ist es eine
// primzahl
printf(" (%d) ",i);
break;
}

}

muss natürlich heissen
if (c>2){ // nicht c<2
break;
}