Methoden Primzahlen

[Kababär]

Hi,

ich habe ein Problem mit einer Aufgabe von ProjectEuler.net :
"What is the largest prime factor of the number 600851475143 ?"

Meine Überlegungen sähen so aus:
1.
Mittels einer for-Schleife die Primzahlen bis 600851475143 ausfiltern. Innerhalb der Schleife soll eine if-Abfrage die Primzahlen bestimmten. Wüsste allerdings noch keine Konkrete abfrage.
Vielleicht

 if ( zahl % 2 != 0) {prim!}

2.
Diese Primzahlen in einer Array speichern und sortieren. Das höchste zuerst oder das niedrigste, egal.
Dann die höchste Primzahl bis 600851475143 als Dividor nehmen und mittels einer if-Abfrage herausfinden, ob das Ergebnis eine Ganzzahl ist oder nicht. Nur wie geht das?
Wenn ja, so soll die nächst kleinere Primzahl genommen werden und mit dem neuen Ergebnis verrechnet werden. Wenn die Primzahl als Dividor gilt, also ein ganzzahliges Ergebnis erzeugen kann, so wird diese Zahl in einem neuen Array gespeichert.
Am Schluss habe ich ein Array mit allen Primfaktoren der Zahl 600851475143 und kann das erste Element des Arrays ausgeben.

3.
Ein Problem: alle Primzahlen bis "600851475143" sind gefragt. Nur reicht da weder int noch long.
Bei

long Zahl = 600851475143;

meint er: "Integer number too large: 600851475143" ! Gibts nichts größeres als long?

Was meint ihr?
Sind meine Überlegungen gut und vor allem realisierbar? Könnt ihr mir ein paar Denkanstöße/Kritik geben?
Die Struktur kommt von mir selbst und die Überlegungen, nur das in einem Code zu verpacken ist dann doch etwas zu schwer für mich. Oder es liegt an meiner Denkweise.

Danke.
LG

 

[XHelp]

1. naja, die Abfrage ist etwas mager, wenn du Primzahlen finden willst. Schau doch einfach mal nach Primzahlentests, alleine hier im Forum gibt es jede Menge Themen.
2. Eigentlich geht man bei Primfaktorzerlegung von der anderen Seite, also fängst du quasi bei der 2 an. Google hier ebenfalls nach einfachsten Begriffen.
3. du gibst auch kein Long an, sondern Integer. Setzt mal ans ende der Zahl ein

L

.

 

[Kababär]

Ich will keine Internethilfen, sondern will es mehr oder weniger alleine schaffen. Darum verzichte ich auf Google-Recherchen und will nur den ein oder anderen Denkanstoß.

Mein Code bisher:

public class No3 {
    
    public static void main ( String []args)
    {
        int zahl = 13195;
        int prime =0; //prime factor
        
        for (int i=1; i<zahl; i++)
        {
        
            if ( zahl % i == 0  )
                prime = i;
            System.out.println(prime);
        }
        
        
    }
    
}

Die Ausgabe:

1
5
7
13
29
35
65
91
145
203
377
455
1015
1885
2639

Allerdings kommt die 1 bis i=5 ist, dann kommt 5 zwei Mal, dann 7 so oft bis i=13 ist etc. Wisst ihr was ich meine?
Und das sind ja nicht nur Primzahlen.

 

[XHelp]

Ich will keine Internethilfen, sondern will es mehr oder weniger alleine schaffen

Dann kommst du wohl nicht drumherum um es einfach mal zu machen, und dann schauen ob es richtig ist, oder nicht :bahnhof:

Verwende geschweiften Klammern bei den If-Abfragen, dann siehst du warum und was ausgegeben wird.
Zu dem Test: der ist falsch. 35 und 65 sind offensichtlich keine Primzahlen.

 

[Tecwan]

Ok, ohne google.
Gut fürs Hirnschmalz.

Du willst eine Schleife implementieren.
Überleg dir, in welchem Bereich du testen musst.
Und ob die Schleife rauf oder runterzählen soll.
Es geht zwar Beides, aber nur eine Richtung ist sinnvoll: rauf.

Wirklich von 1 bis zahl?
Nö. Fang bei der kleinsten Primzahl an, der 2.

Und dann geh nicht weiter als bis ... ? (Wie groß kann der größte Teiler maximal werden?)

Und außerdem: musst du bei jeder Zahl immer auf jede Teilbarkeit testen?
nein, sondern nur auf ... (?)

Und dann: Solltest du dir die gefundenen Primzahlen nicht vielleicht merken?

 

[Kababär]

ich habe doch schon einen Code gepostet:

public static void main ( String []args)
    {
        int zahl = 13195;
        int prime =0; //prime factor
        
        for (int i=1; i<zahl; i++)
        {
        
            if ( zahl % i == 0  )
                prime = i;
            System.out.println(prime);
        }
        
        
    }

@ XHelp: Ich weiß, dass 35 und 65 keine prime factors sind. Das verwundert mich ehrlich gesagt.

@ Tecwan:

Ok, ohne google.
Gut fürs Hirnschmalz.

Ja, ohne google. "Wir denken nicht, wir googlen." Ich bin der Meinung, dass man auch verstehen sollte was man macht und nicht einfach Copy&Paste.
Danke für die Denkanstöße.

Du willst eine Schleife implementieren.
Überleg dir, in welchem Bereich du testen musst.
Und ob die Schleife rauf oder runterzählen soll.
Es geht zwar Beides, aber nur eine Richtung ist sinnvoll: rauf.

Und dann geh nicht weiter als bis ... ? (Wie groß kann der größte Teiler maximal werden?)

Eine Schleife habe ich ja schon. Sie zählt hoch. Anfangen sollte sie bei 2, stimmt, danke, und aufhören sollte sie wohl bis n-halbe, also eher zahl/2.

Und außerdem: musst du bei jeder Zahl immer auf jede Teilbarkeit testen?
nein, sondern nur auf ... (?)

Er muss nicht jede Zahl auf die Teilbarkeit testen, sondern nur die Primzahlen testen?

Und dann: Solltest du dir die gefundenen Primzahlen nicht vielleicht merken?

Doch, die Primzahlen wollte ich mir merken. Dazu habe ich noch eine Frage.
Wenn ich eine if-Abfrage habe, frage ab, ob sie teilbar ist, und ich ganz am Anfang ein Array deklariert habe, kann ich jedes Mal wenn ich eine Primzahl gefunden habe, diese Zahl zum Array hinzufügen?
Dafür gibts sicherlich eine Biblio, aber kann ich meine eigene Methode schreiben?

Um zu verhindern, dass jede Zahl getestet wird, sollte ich vorher wohl schon meine Primzahlen bestimmen?

LG

 

[Marc T.]

Hi,

nutze doch das Sieb des Eratosthenes um die Primzahlen zu finden.

Im prinzip machst du es so:

1. Beginne bei 2
2. Streiche alle vielfachen von 2
3. Gehe zur nächsten Zahl
4. Streiche alle vielfachen dieser Zahl
...

Das machst du so lange, bis du bei der Wurzel der größten Zahl bist.

EDIT:

Code gelöscht, hab erst jetzt gesehen, dass du keine Lösungen willst

 

[Kababär]

Wieso schreibt man ein nevermind?

@ Marc T.: Klingt nach einer guten Idee. Ich habe die Idee etwas geändert:

public static void main ( String []args)
    {
//        
    	
    	long number = 600851475143L;
    	long size = number/2L;
		long [] array = new long[size];
		
		
		// initialize array up to 'groesse'
		for (int i= 0; i<array.length; i++)
		{
			array [i] = i;
		}
		//filter prime numbers out of array
		for (int i=2; i<10; i++)
		{
			for (int a=i*2; a<array.length; a=a+i)
			{
				array [a]=0;
				if (a==a*i) continue; //skip coated multiples
			}
		}
		
		
		//print out the prime number
		for (int i=0; i<array.length; i++)
		{
			if (array[i]!=0)
			
				System.out.print(array [i]+" ");
			
		}
        
        
    }

Allerdings sagt er mir, dass "Type dismatch: cannot convert from long to int." bei "long [] array = new long[size];"
Woran liegt das? Ich benutze doch gar kein int mehr bei dem Array, weil long[]... und size ja auch long ist?

Was der Codeschnipsel macht, ist, nach dem Sieb des Eratosthenes die Primzahlen bis 600851475143/2 rauszusuchen und diese auszugeben.

Jetzt fehlt mir noch, dass ich diese speichere und auf die Teilbarkeit überprüfe.
Die Teilbarkeit ist ja kein Problem, aber wie kann ich sie abspeichern? Ich würde sie gern in einem Array abspeichern.
Kann man so Primzahlen hinzufügen?

int primeArray[]; //list of prime numbers
...
...
...
...
   for (int i=1; i<size; i++)
        {
        for(int j=0; j<size; j++)
            if ( zahl % i == 0  )
                prime = i;
                primeArray[0+j]=prime; //adding a prime numbers if it's dividor and a prime 
   }}}

Mir selbst dreht es den Magen rum bei diesem Code...

 

[Marc T.]

Du hast die Primzahlen doch schon gespeichert.

In dem Array wo du jede nicht Primzahl als "0" markiert hast
stehen alle Primzahlen drin. Oder hab ich dich nicht richtig
verstanden?

 

[Paddelpirat]

In diesem Fall

long [] array = new long[size];

muss

size

ein Integer sein.

Edit: Außerdem wirst du wesentlich weniger Primzahlen haben, da nicht jede zweite Zahl eine Primzahl ist.

 

[Tecwan]

EDIT: Post geschrieben, während andere Antworten eintrafen

Ok, nächster Schritt.

Mit der Obergrenze von n/2 bist du nur ein kleines Stück weiter gekommen.
Es lässt sich aber noch viel mehr eingrenzen.
Ich denke mal, ich verrate nicht zuviel, wenn ich darauf hinweise, dass
Testzahl > größte Teiler-Primzahl * größte Teiler-Primzahl
ist. Also nicht nur die Hälfte, sondern nur ...
(Drüber nachdenken, gibt ein Aha dafür!)

Und ja, man braucht nur die Primzahlen zum Teilen.

Du kannst natürlich nach einer Bibliothek suchen (wobei das Primzahlenverzeichnis noch effektiver
wäre, aber das ist ja kaum der Sinn der Sache), aber eine eigene Methode ist nicht so schwer.

Definiere dir ein Array:

long[] prim = new long[x];

wobei x die Anzahl der vermuteten Primzahlen ist; man kann zwar auch Datenstrukturen erzeugen,
bei denen man vorher nicht wissen muss, wieviele Variablen sie nachher enthalten, aber einfacher
ist am Anfang sowas hier.
Wenn die Größe nicht ausreicht, kannst du die Zahl ja einfach erhöhen.

Und dann trenne deine Aufgabe in zwei Teile:
- die Schleife, bei der du die Zahl hochzählst:
ist die Zahl eine neue Primzahl, dann füge sie dem Array hinzu und merke dir, die wievielte es ist;
ist sie es nicht, dann nimm die nächste Zahl in der Schleife. In der Schleife musst du natürlich alle
Zahlen testen - jede könnte eine Primzahl sein. Nur durch welche Zahlen die Testzahl geteilt werden
muss, das reduziert sich gewaltig.
- die Bestimmung, ob eine Zahl eine Primzahl ist. Dazu brauchst du nur die Teilbarkeit der Zahl durch
alle bekannten (kleineren) Primzahlen bis zur für die Testzahl gültigen Obergrenze abfragen. Das ist
wieder eine Schleife, die du am Besten in eine Methode

Boolean isPrimzahl(long testzahl){...}

packst.

Also musst du dir nur noch merken, wieviele Primzahlen du bereits kennst.
Und wenn du deine Riesenzahl (bzw. die Obergrenze) erreicht hast, ist die letzte Primzahl die
gesuchte.
Du brauchst also nicht erst eine Tabelle aufstellen, sondern kannst gleich alles in einem Aufwasch
machen.

 

[Tecwan]

Nachtrag:
Für die Zahl der benötigten Feldelemente reicht int (32 bit) als Index für das Array noch aus.
Übrigens auch das Feld der Primzahlen selbst darf vom Typ int[] sein.

Das Sieb des Erastothenes 1:1 umzusetzten, wird übrigens Probleme bereiten, wenn für jede Zahl ein
Array-Element belegt werden muss.
600 Millarden longs (64 bit) verbrauchen 4.8 Billionen Byte...
Es gibt viel mehr Nicht-Primzahlen als Primzahlen, und selbst die notwendigen verbleibenden sprengen
fast den Rahmen.
300 Millarden longs sind nicht wesentlich besser...

Also: Obergrenze herausfinden, und dann den Test so schreiben, das man sich wirklich nur die Primzahlen merkt und nicht all die 0er.
Außerdem ist es sinnvoll den Test zwar gleich für die große Zahl zu schreiben, aber an einer kleineren bekannten auszuprobieren.


Noch ein Tip:
Wenn eine Variable in einen anderen Typ umgewandelt werden muss, kann man das so machen:
Beispiel für das sog. Casten:

float v = 1234.567;
int z = (int) v;

Bei z fehlen dann allerdings die Nachkommastellen - man muss sich darüber im Klaren sein.
die Umwandlung long <=> int funktioniert genauso (falls es der Wertebereich zulässt!)

 

[SebOeh]

Übrigens, um den höchsten Primfaktor einer Zahl herauszufinden mußt Du höchstens nur bis zur Quadratwurzel dieser Zahl probieren. Besipielsweise für die Zahl 1234 brauche ich nur die Primzahlen bis sqrt(1234) ~35 zu testen. Das sind schon mal viel weniger Zahlen die Du testen mußt. Ich glaube das sind die Hälfte, da die Dichte der Primzahlen nach oben abnimmt.

 

[Landei]

Du brauchst für die Aufgabe keine einzige Primzahl zu bestimmen. Du beginnst bei 3, Schrittweite 2. Immer wenn du eine Zahl findest, durch die deine Ausgangszahl teilbar ist, teilst du diese auch (so oft wie möglich). Kommst du mit der Schleife über die Wurzel der Restzahl hinaus (siehe SebOehs Ausführungen), ist die Restzahl selber der größte Primfaktor.

Beispiel 245: Nicht durch 3 teilbar, aber durch 5. 245:5 = 49. 49 ist nicht durch 5 teilbar, aber durch 7. 49:7 = 7, und unser Schleifenindex 7 ist schon größer als Wurzel 7 = 2,64575.. Also ist 7 der größte Primfaktor von 245.

 

[Kababär]

@ Marc T.: Nein, ich gebe nur durch Sysout die Primzahlen aus, speichere sie doch aber gar nicht...

@ Tecwan: Den Array habe ich schon

long size = 600851475143L^1/2;
    	int size2 = (int) size;
		int [] array = new int[size2];

doch er sagt mir:

Exception in thread "main" java.lang.NegativeArraySizeException
	at No3.main(No3.java:3)

Der Array muss nur so groß sein wie die Wurzel meiner Zahl.
Die Methode, dass ich die Primzahlen raussuche, habe ich ja auch schon:

for (int i=2; i<10; i++)
		{
			for (int a=i*2; a<array.length; a=a+i)
			{
				array [a]=0;
				if (a==a*i) continue; //skip coated multiples
			}
		}

Vermutlich hast du aber Recht und ich sollte mir eine eigene Methode mit dem Typ boolean zulegen, aber das wäre doch schon ein Optimierungsschritt, oder? Aber je schneller, desto besser.

@ SebOeh: Hilfreicher Tipp, danke.
@ Landei: Wenn ich schrittweise +=2 hochzähle und auf die Teilbarkeit überprüfe, komm ich so auf jede Primzahl? Was sit mit den Zahlen, die keine Primzahlen sind? (9, 15, 25, 33, ... ?)

 

[SebOeh]

... Du beginnst bei 3, Schrittweite 2. Immer wenn du eine Zahl findest, durch die deine Ausgangszahl teilbar ist, teilst du diese auch (so oft wie möglich). Kommst du mit der Schleife über die Wurzel der Restzahl hinaus (siehe SebOehs Ausführungen), ist die Restzahl selber der größte Primfaktor.

Das stimmt leider nicht ganz, da zB bei der Zahl 1365 müßte man bis 35 probieren. 35 teilt 1365, 35 ist aber keine Primzahl.
Man kann es aber trotzdem machen, indem in einem weiteren Druchlauf der gefundene größte Divisor danach getestet wird, ob er eine Primfaktorzahl hat. Wenn er eine hat, dann muß man den vorigen Divisor testen. Das bedeutet, man soll alle Divisoren in einem Array (oder Liste) erst mal speichern.

 

[Kababär]

Das bedeutet, man soll alle Divisoren in einem Array (oder Liste) erst mal speichern.

Und genau das ist mein Problem. Wie mach ich das? Den Rest des Codes hätte ich.

for (int i=3, i<=zahl^1/2; i+=2)
{
   if (zahl%i == 0 )
   ?????;
}

Gibt es nicht sowas wie:

add.to.array();

Oder:

if (zahl%i = 0 )
 array[+i]; //add when 'if' is true

 

[SebOeh]

@ Tecwan: Den Array habe ich schon...

Wenn Du nicht weiß, wie lang ein Array wird, und immer die Gefahr siehst, daß Du den zu klein geplant hast, empfehle ich Dir stattdessen eine Liste (LinkedList) zu verwenden. Da kannst Du beiliebig viele Elemente (in diesem Fall vom Typ "Integer", keine "int", oder "Long" und nicht "long") speichern kannst.
Ungetesteter Beispiel:So macht man eine Liste, fügt Elemente hinzu und verwandelt man sie in ein array:

package deinPaket;
import java.util.LinkedList;
public class Temp {
	public static void main(String[] args){
		LinkedList<Integer> meineListe = new LinkedList();
		meineListe.add( neuerWert() ); //fügt ein Element der Liste hinzu
		Integer[] meinFeld = new Integer[ meineListe.size() ];
		meineListe.toArray(meinFeld); // jetzt ist alles in mein Feld
	}
	static Integer neuerWert(){ return 4;	}
}

Für die Bestimmung der Primzahlen empfehle ich Dir die Zahlen aus dem Internet herunterzuladen und in einem array in Deinem Programm zu speichern. Sonst würdest Du jedes mal die Liste der Primzahlen neu berechnen. Das wäre so umfangreich und Programmzeit-verschwenderisch wie jedes mal die Zahl Pi als long neu zu berechnen, wenn man sie braucht. Stattdessen ist sie fest in Java gespeichert. Schade eigentlich, daß die Liste der Primzahlen kein fester Bestandteil der Klasse Math ist. Schau mal zB hier: Wikipedia - Liste der Primzahlen.

Wenn Du sie nicht findest oder doch selber rechnen willst, dann brauchst Du das nur einmal in Deinem Leben zu machen und irgendwo speichern, daß Du die Liste wieder aufrufen kannst.

 

[Paddelpirat]

Schade eigentlich, daß die Liste der Primzahlen kein fester Bestandteil der Klasse Math ist.

Wie sollte es in Java eine Liste geben? Es ist ja nicht so, dass in der Wikipedia-Liste alle Primzahlen sind, die es überhaupt gibt.

 

[SebOeh]

Wie sollte es in Java eine Liste geben? Es ist ja nicht so, dass in der Wikipedia-Liste alle Primzahlen sind, die es überhaupt gibt.

Und wie kann es dann PI geben? Das passt doch auch in keine long-Zahl ein. Antwort: Man muß in einem Forum nicht unbedingt immer so pingelich lesen, um zu verstehen. Es sind auch nicht mal alle natürlichen Zahlen darstellbar Du Schlaumeier.

 

[Dekker]

Und wie kann es dann PI geben? Das passt doch auch in keine long-Zahl ein.

Sorry, musste grade hier dran denken. :lol:

 

[Paddelpirat]

Und wie kann es dann PI geben?

Pi ist ein approximierter Wert. Klar ist der ungenau, aber reicht im Normalfall für die meisten Berechnungen aus.

Vielleicht hätte ich statt "wie" das Wort "wieso" verwenden sollen. Das Problem, welches ich bei einer Liste der Primzahlen sehe ist die Frage, wo man sie beenden sollte. Eine Liste die die Primzahlen zwischen 2 und 100000 liefert braucht sicherlich kein Mensch, außer für ein kleines Test-Programm. Wenn man in die Richtung Verschlüsselung geht, hat man es mit DEUTLICH größeren Primzahlen zu tun.

 

[Landei]

Das stimmt leider nicht ganz, da zB bei der Zahl 1365 müßte man bis 35 probieren. 35 teilt 1365, 35 ist aber keine Primzahl.
Man kann es aber trotzdem machen, indem in einem weiteren Druchlauf der gefundene größte Divisor danach getestet wird, ob er eine Primfaktorzahl hat. Wenn er eine hat, dann muß man den vorigen Divisor testen. Das bedeutet, man soll alle Divisoren in einem Array (oder Liste) erst mal speichern.

Hast du mein Beispiel richtig gelesen? Wenn du einen Teiler findest, musst die Zahl auch teilen...

1365 ist durch 3 teilbar -> 455
455 ist durch 5 teilbar -> 91
91 ist durch 7 teilbar -> 13
wir müssten jetzt mit dem Test auf 9 weitermachen, aber die ist schon größer als Wurzel aus 13, also ist 13 der gesuchte größte Primfaktor von 1365.

 

[Kababär]

Bei

long size = 600851475143L^1/2;
    	int size2 = (int) size;
		int [] array = new int[size2];

Kommt eine Fehlermeldung

Exception in thread "main" java.lang.NegativeArraySizeException
	at No3.main(No3.java:18)

Hier: No3.java:3

Wieso ist dort die Zahl size2 negativ?
Falsch umgewandelt?

 

[Paddelpirat]

Das kommt, weil ein Long wesentlich größere Werte als ein Integer annehmen kann und du dann beim Cast auf einen Integer einen Überlauf hast, der in deinem Fall zu einem negativen Wert führt.

Edit: Hier findest du die Wertebereiche der unterschiedlichen Datentypen: Java-Syntax ? Wikipedia

Edit 2: Dein

long size = 600851475143L^1/2;

sieht im übrigen auch etwas schief aus. Probier es eher mal mit

long size = Math.round(Math.sqrt(600851475143))

oder noch besser, wie vorher schon vorgeschlagen wurde eine Liste verwenden.

 

[Kababär]

Also selbst zahl/2 kann von int nicht repräsentiert werden.
Das heißt ich muss den primitiven Datentyp long doch verwenden und ebenfalls in mein Objekt Array mit einbauen, damit dieser auch ein Element des Umfangs der Zahl zahl erzeugen kann.

Also streiche ich das casten und nun sieht mein Code so aus

long size = 600851475143L^1/2;
    	
		long [] array = new long[(int)size];

spuckt aber immer noch die selbe Fehlermeldung aus.
Ohne das (int) in [] unterstreicht mir Eclipse das size, weil er nicht von long zu int konvertieren kann.
Mach ich aber daraus ein int, dann kommt eine NegativeArraySizeException raus.

Meine Idee dazu war simpel, den Index*(-1) zu nehmen

long [] array = new long[((int)size)*(-1)];

allerdings kommt dann:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Wenn ich

long size = -600851475143L^1/2;

schreibe, kommt die selbe Fehlermeldung.

Eventuelle Denkanstöße? Was mach ich noch falsch? Ist die Aufgabe evtl. noch zu schwer für mich, weil ich nur Grundlagen kenne?

Edit: @ Paddelpirat: Eigentlich wollte ich Implementierungen vermeiden. Ich finde es sieht einfach nicht so schön aus, wenn man Befehle aus Bibliotheken verwendet. So könnte ich ganz einfach und simpel den Code zusammenbasteln. Man vergleiche nur den Aufwand beim Programmieren von Palindromes mit und ohne Bibliotheken.. obwohl es ohne gar nicht gehen sollte..

Mit Listen habe ich noch nie gearbeitet. Da ich sowieso nur den größten 'prime factor' haben will, kann ich doch auch einfach die zuletzt ausgegebene Primzahl merken:

//print out the prime number
		for (int i=0; i<array.length; i++)
		{
			if (array[i]!=0)
			
				System.out.print(array [i]+" ");
			
		}

Sowas in der Art wie

biggestPrimeFactor = array[MAX(i)]

?
Oder will ich grad das Rad neu erfinden?

 

[Paddelpirat]

Das Problem mit deinem ^1/2 ist aber dass es nicht das macht, was du willst. ^ ist in Java ein bit-Weises Oder und kein Potenzzeichen: Bitwise and Bit Shift Operators (The Java™ Tutorials > Learning the Java Language > Language Basics)

Deswegen solltest du in so einem Fall Math.sqrt und Math.round verwenden.

In der Programmiersprache Python dagegen könntest du das ^ als Pozenzsymbol verwenden, aber selbst dann müsste es 600851475143L^(1/2) heißen, da du sonst zuerst hoch 1 rechnest und anschließend das Ergebnis durch 2 teilst. Klammersetzung ist wichtig!

Nun zu deinem Code:

long size = 600851475143L^1/2;
        
long [] array = new long[(int)size];

Du führst den Cast von Integer zu Long nun zwischen den eckigen Klammern aus. Dadurch ist nichts gewonnen, weil dein Long immer noch zu groß ist, als das er ohne Probleme auf einen Integer gecastet werden kann.
Da du aber nicht weißt wie viele Primzahlen du finden wirst, bietet es sich hier wirklich an eine Liste zu verwenden.

 

[Kababär]

Ok, ich sehs ein.
Ich importieren die benötigten Biblios und wage mich mal auf ins neue Land.

Mal sehen, ob ich das mit den Listen hinbekommen werde....

Danke bis hierhin.

 

[Tecwan]

Ein Rat: Keine Listen, es geht ohne, und es sind weniger als 64000 Primzahlen.

Ich gebe dir mal etwas Code, der aber nicht vollständig ist.
(long) Math.sqrt(zahl) berechnet (für diese Zwecke) die Wurzel.

int[] prime = new int[64000];
int primeCount = 0;
prime[0]=2;
long number = 600851475143L;

for (long i=2; i<(long) Math.sqrt(number); i++) {
    //Kontrolle auf neue Primzahl und Registrierung in prime[]    
}
//Ausgabe des Ergebnisses

static Boolean isPrime(long zahl) {
    // Schleife, bei der die vorhandene Liste der Primzahlen benutzt wird    
}

 

[Kababär]

Ich glaube die Aufgabe ist zu schwer für mich, ich hänge momentan :bahnhof:

Liegt vielleicht daran, dass ich mir Vorlesungen zu Java reinziehe und bei Gailer nebenbei lerne.

 

[Paddelpirat]

Vielleicht einfach mal ein Java-Buch oder ein ausführliches Tutorial nehmen und da Schritt für Schritt durchgehen, wenn du meinst die gelesenen Kapitel verstanden zu haben, kannst du Übungsaufgaben zum Thema abarbeiten, oder dir selber kleinere Aufgaben ausdenken.

So kannst du dich auch Schritt für Schritt in neuere Themen einarbeiten.

 

[Tecwan]

Ich glaube die Aufgabe ist zu schwer für mich, ich hänge momentan

Sag doch sowas nicht...

Es fehlen in dem Code nur ein paar wenige Zeilen.

In der ersten Schleife gehst du alle Zahlen durch und überprüfst, ob sie Primzahlen sind.
Das kannst du mit der Methode isPrim(i) tun.
Wenn i eine Primzahl ist, dann merkst du sie dir:

prim[++primeCount] = i;

Mehr ist da nicht zu tun.
Ist die Schleife fertig, hast du alle Primzahlen bis number gefunden, und du musst nur noch
überprüfen, durch welche dieser Zahlen number ohne Rest teilbar ist.
- Das kannst du in einer zweiten abwärts von primeCount zählenden Schleife tun - wobei
der erste Treffer das Ergebnis ist -,
- oder du merkst dir bereits in der ersten Schleife, ob die gerade gefundene Primzahl auch
ein Teiler von number ist. Der zuletzt gefundene Teiler ist dann auch der größte.
Sinnvollerweise lässt du dir aber alle Teiler von number ausgeben, um das Ergebnis zu kontrollieren.

Die Methode isPrime() ist simpel, ich gebe sie dir mal vor:

static Boolean isPrime(long zahl) {
    Boolean ret = true;
    for (int p=0; p<primeCount; p++) {
        if (zahl % prime[p] == 0) {
            ret = false;
            break;
        }
    }
    return ret;
}

Sie besteht aus einer Schleife, in der du du die zu testende Zahl der Reihe nach durch alle
bisher gefundenen Primzahlen teilst und auf Rest prüfst.
Existiert bei einer Division kein Rest, dann kannst du die Schleife abbrechen, weil zahl keine
Primzahl sein kann.

 

[Kababär]

Danke

Ich bin dabei, erstmal die Basics zu festigen und alles 100%ig zu verstehen. Morgen kommt endlich mein Java Buch "Head First Java".

Wenn ich das habe, werde ich mir das Software Development Buch durchlesen. Danach werde ich mich in AWT&Swing einlesen und so dann immer Schritt für Schritt weiter.
Mal Kartenspielen, Sudoku, Mikado, Taschenrechner, Minesweeper, Solitaire, Puzzle, Mahjong, etc.


@ Tecwan: Mein Programm ist für mich null-überschaubar, da ich von jedem Vorschlag ein bisschen reingepflanzt hab und gar nicht mehr weiß wo hinten und vorne ist, ... tut mir leid.

 

[Tecwan]

kein Problem.
Nimm dir Zeit, gerade auch für die theoretischen Grundlagen.
Code schreiben ist relativ leicht zu lernen - Probleme so zu zerlegen, dass daraus leicht zu schreibender
Code wird, aber nicht.


Und falls es wieder mal jemand versucht:
Die Testzahl hat nur vier Teiler, und der höchste davon sogar nur vier Stellen.
Und günstigerweise kommt jeder der Teiler auch nur einfach vor.

Wenn man zusätzlich einen Test einbaut, ob aus den gefundenen Primzahlen bereits die Testzahl zusammengesetzt
werden kann, ist die Berechnung in einer Sekunde fertig und kann abgebrochen werden, anstelle dann eine weitere
halbe Minute bis zum Erreichen der Obergrenze rechnen zu müssen.
Hier reichen die ersten 900 Primzahlen locker aus, ansonsten müssen es über 63.000 werden...