java"noob" mit frage zu eleganz

[Uni]

folgende aufgabe: ich soll ne zahl eingeben und das prog wirft aus, obs ne primzahl is, oda obs keine is.
die frage: is das ne elegante lösung oda gehts irgendwie "besser"?

class Prim
{
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]); // angegeben Zahl
int i; // testteiler
int t; // testteiler
int m; // vergleichs mod
int j; // vergleichs mod

i=2;
t=3;
m=n%i;
j=n%t;

if((j>0)&&(m>0)) //wenn der rest beider divisionen größer
{ //als 0 ist, dann ist die Zahl eine Primzahl
System.out.printf("%d ist eine Primzahl",n);
}
else
System.out.printf("%d ist keine Primzahl",n);
}
}

[ethrandil]

Algorithmisch gehts noch... schneller und anders, siehe http://de.wikipedia.org/wiki/Primzahl#Verfahren_zur_Pr.C3.BCfung_der_Primalit.C3.A4t_einer_Zahl .

Und um den code umzustellen solltest du ihn erstmal in [code]-Tags setzen, damit man ihn vernünftig anschauen kann :)

- Eth

[Senior Sanchez]

folgende aufgabe: ich soll ne zahl eingeben und das prog wirft aus, obs ne primzahl is, oda obs keine is.
die frage: is das ne elegante lösung oda gehts irgendwie "besser"?

class Prim
{
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]); // angegeben Zahl
int i; // testteiler
int t; // testteiler
int m; // vergleichs mod
int j; // vergleichs mod

i=2;
t=3;
m=n%i;
j=n%t;

if((j>0)&&(m>0)) //wenn der rest beider divisionen größer
{ //als 0 ist, dann ist die Zahl eine Primzahl
System.out.printf("%d ist eine Primzahl",n);
}
else
System.out.printf("%d ist keine Primzahl",n);
}
}


Öhm, ich meine das der Algorithmus falsch ist.
Versuche mal 25. Er sagt bestimmt das es prim ist, hm?

[Marscel]

// Class, Function, was weiß ich...
int Zahl;
int i = 1;
bool primzahl = 0;

while((i-1) != Zahl)
{
if(i != 1)
{
if(Zahl%i == 0)
{
primzahl = 1;
break;
}
}
i++;
}

if(primzahl)
{
// Meldung
}

//Ende


Kann das eher hinkommen? Wenn nicht, ich bin schon halb im Bett...

[Senior Sanchez]

// Class, Function, was weiß ich...
int Zahl;
int i = 1;
bool primzahl = 0;

while((i-1) != Zahl)
{
if(i != 1)
{
if(Zahl%i == 0)
{
primzahl = 1;
break;
}
}
i++;
}

if(primzahl)
{
// Meldung
}

//Ende


Kann das eher hinkommen? Wenn nicht, ich bin schon halb im Bett...


wenn nen bool 0 zugewiesen bekommt ist das false oder true?
Ich habs jetzt net getestet, aber vom rüberschauen würde ich sagen, dass es falsch ist.
wenn bool 0 = false und 1 = true gehts für 4 schief
anderenfalls gehts für 1 schief

[KhanRKerensky]

So hab ich das mal in Python gemacht:
def isPrime(x):
if x < 2:
return 0
if x < 4:
return 1
if not(x%2):
return 0
for i in range(3, math.sqrt(x) + 2, 2):
if ((x%i) == 0):
return 0
else:
return 1

Die Funktion ist eigentlich ganz einfach.
Zuerst fang ich ein paar Sonderfälle ab.
Alles kleiner 2 ist keine Primzahl.
2 und 3 werden als Prim direkt zurückgeworfen.
Dann wird alles aussortiert was ohne Rest durch 2 teilbar ist.
Danach durchlauf ich alle ungeraden Zahlen von 3 ab bis zur Wuzel der zu prüfenden Zahl auf eine Teilbarkeit ohne Rest. Die +2 bei der Wurzel hängt mit einer Eigenart von der Funktion range ab. Ich möchte incl. der Wurzel testen und Range macht das ohne die +2 nicht ;)

Ein einfacher Siebalgo testet also nur jede zweite Zahl ab der 3 bis zur Wurzel von x. Da man die Zahlen kleiner 3 damit nicht behandelt muss man die gesondert behandeln, aber das ist es wert.

[Gast]

So hab ich das mal in Python gemacht:
def isPrime(x):
if x < 2:
return 0
if x < 4:
return 1
if not(x%2):
return 0
for i in range(3, math.sqrt(x) + 2, 2):
if ((x%i) == 0):
return 0
else:
return 1

Die Funktion ist eigentlich ganz einfach.
Zuerst fang ich ein paar Sonderfälle ab.
Alles kleiner 2 ist keine Primzahl.
2 und 3 werden als Prim direkt zurückgeworfen.
Dann wird alles aussortiert was ohne Rest durch 2 teilbar ist.
Danach durchlauf ich alle ungeraden Zahlen von 3 ab bis zur Wuzel der zu prüfenden Zahl auf eine Teilbarkeit ohne Rest. Die +2 bei der Wurzel hängt mit einer Eigenart von der Funktion range ab. Ich möchte incl. der Wurzel testen und Range macht das ohne die +2 nicht ;)Es gibt ca. unendlich viele Primzahlen, fängst aber im Gegenzug ganze zwei Sonderfälle ab. Ist das niedlich, hehe. ;D

[Abnaxos]

wenn nen bool 0 zugewiesen bekommt ist das false oder true?
Wir reden von Java, also: Nichts von beidem, das kompiliert nicht.

[Monger]

wenn nen bool 0 zugewiesen bekommt ist das false oder true?
Ich habs jetzt net getestet, aber vom rüberschauen würde ich sagen, dass es falsch ist.
wenn bool 0 = false und 1 = true gehts für 4 schief
anderenfalls gehts für 1 schief

1 ist keine Primzahl! ;)

Eine Primzahl muss durch sich selbst UND durch 1 teilbar sein. Zumindest zu meiner Schulzeit war 1 per Definition keine Primzahl.

[Aqualon]

1 ist keine Primzahl! ;)

Eine Primzahl muss durch sich selbst UND durch 1 teilbar sein. Zumindest zu meiner Schulzeit war 1 per Definition keine Primzahl.Darüber lässt sich streiten. Oft gehen die Primzahlen erst bei 3 los, aber rein von den Bedingungen her müssten 1 und 2 auch Primzahlen sein.

Aqua

[Senior Sanchez]

Wir reden von Java, also: Nichts von beidem, das kompiliert nicht.

Das es kein Java war, das war mir durchaus bewusst, ansonsten hätte ich nicht nach dem Datentyp bool gefragt. ;) Und ich glaube, es ging jetzt mehr um den grundsätzlichen algorithmus, oder?


1 ist keine Primzahl!

Eine Primzahl muss durch sich selbst UND durch 1 teilbar sein. Zumindest zu meiner Schulzeit war 1 per Definition keine Primzahl.


Das sagt der richtige.
das ist mir bewusst, nur du weißt es anscheinend nicht ;) Denn dein Algorithmus ist falsch. Du hast mir zwar immernoch nicht erklärt, ob bool primzahl = 0 true oder false bedeutet, aber egal welcher fall, dein algo ist falsch.
Aber ums nochmal zu erläutern:
Angenommen bool = 0 bedeutet true und bool = 1 bedeutet false, so ergibt sich für deinen Fall bei der Zahl 1 ein Fehler.
1 ist keine Primzahl, aber schau dir mal an was bei dir inner schleife passiert.
1. Durchlauf:
while( 1 -1 != 1) --> true, läuft weiter
weil i aber 1 ist, wird nur inkrementiert.
2. Durchlauf:
while( 2 -1 != 1) --> false, die bedingung stimmt nicht, weil 2-1 eben 1 ist
somit geht er nicht nochmal rein und gibt im if-block, der denke ich mal nur bei primzahlen ausgegeben wird aus, das 1 ne primzahl ist. ist aber eben falsch.

Andersherum bei bool = 1 bedeutet true und bool = 0 bedeutet false, gehts für 4 schief.

Denn im zweiten Durchlauf ergibt die Modulo-Operation 4 % 2 eben 0, somit wird bool auf 1 gesetzt und am ende eben wieder ausgegeben.
Aber 4 ist nun mal keine primzahl.


EDIT: Aber warum man sich da so schwer tut, ist doch ganz easy. Das ist jetzt net der cleverste und schnellste Algo, sondern er prüft einfach ganz trivial die nötige Bedingung und das funzt ohne Probleme. Will man natürlich Geschwindigkeit, so sollte man andere Verfahren verwenden.


public class Primtest {

public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
boolean prime = true;

if(n == 1) {
prime = false;
}

for(int i= 2; i < n; i++) {
if(n%i == 0) {
prime = false;
break;
}
}

if(prime) {
System.out.println(n + " ist eine Primzahl.");
}
else {
System.out.println(n + " ist keine Primzahl.");
}

}

}

[Trap]

Normal ist in C/C++:
!0==true, 0==false (oder in Worten: nur 0 ist falsch, alles andere ist wahr)

[Senior Sanchez]

Normal ist in C/C++:
!0==true, 0==false (oder in Worten: nur 0 ist falsch, alles andere ist wahr)

Dachte ich es mir doch, aber ich wollte lieber mal nachfragen.
Trotzdem danke für die Aufklärung Trap :)

[KhanRKerensky]

Es gibt ca. unendlich viele Primzahlen, fängst aber im Gegenzug ganze zwei Sonderfälle ab. Ist das niedlich, hehe. ;D

Ja. Ich hab allerdings drei Gründe, warum ich alles kleiner 4 gesondert behandle.
- x < 2 Damit fang ich einerseits die 1 ab und zudem noch alle negativen Zahlen. Damit spar ich etwas laufzeit und ich muss keine negative Wurzel ziehen.
- 2 selbst ist die einzige Primzahl die Gerade ist. Wenn ich die 2 innerhalb der Schleife behandeln wollte müsste ich jede Zahl zwischen 2 und sqrt(x) testen. So hab ich nur jede zweite.
- Die 3 funktioniert einfach mit der Schleife nicht ;). Da spielt range() nicht mit.

Was die Diskussion angeht was überhaupt ne Primzahl ist und was nicht empfehle ich mal Wikipedia:
http://de.wikipedia.org/wiki/Primzahlen

[Marscel]

Dachte ich es mir doch, aber ich wollte lieber mal nachfragen.
Trotzdem danke für die Aufklärung Trap :)

Tut mir Leid, ich hänge zu viel am paraliberalen PHP.

Mein Vorschlag geht nicht...

EDIT, so, nun aber:
- Annahme, dass alle Zahlen Primzahlen sind (bool primzahl = true;)
- Wenn die eingegebene Zahl (int X) 1 oder 2 ist, ist es eine Primzahl, primzahl bleibt true, Funktion zu Ende.
- Nun wird X auf restlose Teilbarkeit durch die Zahlen 2 bis X-1 geprüft
- Ergibit die Prüfung, dass die Teilbarkeit mit einer Zahl zwischen 2 und X-1 restlos ist, handelt es sich um keine Primzahl mehr (primzahl = false;), die Schleife wird beendet um weitere Schritte zu sparen.

[Kinman]

Ich hab das ganze jetzt nur überflogen, also kann sein das folgende möglichkeit nicht zielführend und/oder schon gepostet wurde:
Mit dieser Methode prüfe ich allerdings nicht auf Primzahlen, sondern Berechne alle Primzahlen bis zu einem bestimmten Wert:

1. Man nehme ein Boolean Array von 1 - höchste Zahl
2. Alles auf TRUE setzen
3. Alle Multiplikationen bis zur max. Zahk durchgehen* (2*1, 2*2, 2*3, .... 3*2, 3*3, ...)
4. Array auslesen: Überall wo TRUE drinsteht ist eine Primzahl
--------
*) Hier steht das größte Optimierungspotential:
Zuerst prüfen ob die Zahl mit der man Multiplizieren will noch auf 1 steht, 2 zuerst berechnen wie weit man Multiplizieren muss, um zu dem letzten Wert zu kommen.

Angenommen ich berechne alle Primzahlen von 1-10 (einfachhalber sag ich auch das 1,2,3 eine Primzahl ist)

Das Array am Start:
1111111111

Nach dem ersten Durchgang (2*1, 2*2, 2*3,....)
1110101010

Zweiter Druchgang (3 ist noch 1, somit 3*3, (3*2 war ja schon), 3*4 -> wäre eh schon drüber, fällt somit weg
1110101000

Dritter Durchgang: kleinste neue wäre 4*4 -> schlägt aber drüber, somit fertig.

Das ganze ist relativ schnell, vllt werde ich das mal in C++ oder C# ausprogrammieren.

mfg Kinman

[Senior Sanchez]

Ich hab das ganze jetzt nur überflogen, also kann sein das folgende möglichkeit nicht zielführend und/oder schon gepostet wurde:
Mit dieser Methode prüfe ich allerdings nicht auf Primzahlen, sondern Berechne alle Primzahlen bis zu einem bestimmten Wert:

1. Man nehme ein Boolean Array von 1 - höchste Zahl
2. Alles auf TRUE setzen
3. Alle Multiplikationen bis zur max. Zahk durchgehen* (2*1, 2*2, 2*3, .... 3*2, 3*3, ...)
4. Array auslesen: Überall wo TRUE drinsteht ist eine Primzahl
--------
*) Hier steht das größte Optimierungspotential:
Zuerst prüfen ob die Zahl mit der man Multiplizieren will noch auf 1 steht, 2 zuerst berechnen wie weit man Multiplizieren muss, um zu dem letzten Wert zu kommen.

Angenommen ich berechne alle Primzahlen von 1-10 (einfachhalber sag ich auch das 1,2,3 eine Primzahl ist)

Das Array am Start:
1111111111

Nach dem ersten Durchgang (2*1, 2*2, 2*3,....)
1110101010

Zweiter Druchgang (3 ist noch 1, somit 3*3, (3*2 war ja schon), 3*4 -> wäre eh schon drüber, fällt somit weg
1110101000

Dritter Durchgang: kleinste neue wäre 4*4 -> schlägt aber drüber, somit fertig.

Das ganze ist relativ schnell, vllt werde ich das mal in C++ oder C# ausprogrammieren.

mfg Kinman


Du beschreibst das Sieb des Eratosthenes. Das zäumt das ganze von hinten auf. Man findet erst alle Primzahlen bis dorthin und prüft dann einfach übers Array, obs ne Primzahl ist.
Kann man natürlich auch machen, aber ich wollts einfach und übersichtlich halten.

[Kinman]

Hehe, danke jetzt hab ich endlich einen Namen dafür. Das ganze ist allerdings (schon vor ein paar Jahren) auf meinem Mist gewachsen, ohne dass ich den Algorithmus schon gekannt habe ;)

EDIT: Perfekt beschrieben ;) http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

mfg Kinman

[Senior Sanchez]

Hehe, danke jetzt hab ich endlich einen Namen dafür. Das ganze ist allerdings (schon vor ein paar Jahren) auf meinem Mist gewachsen, ohne dass ich den Algorithmus schon gekannt habe ;)

mfg Kinman

Der praktikable Standardalgorithmus für Primzahlen, sofern man net besonders viele oder alles besonders schnell braucht ;)
Ich hatte das Sieb auch mal testweise für jemanden mit mehreren Threads gemacht, aber leider nie auf nem DualCore/Multi-CPU System probiert.

[Kinman]

Der praktikable Standardalgorithmus für Primzahlen, sofern man net besonders viele oder alles besonders schnell braucht ;)
Ich hatte das Sieb auch mal testweise für jemanden mit mehreren Threads gemacht, aber leider nie auf nem DualCore/Multi-CPU System probiert.

Funktionieren Multithreaded noch alle Optimierungen? Ich denke nicht, oder?

[Senior Sanchez]

Funktionieren Multithreaded noch alle Optimierungen? Ich denke nicht, oder?

Multithreaded wirds schwer, zu mal die Sinnhaftigkeit infrage zu stellen ist. Es war die Aufgabenforderung, aber es war einfach blödsinnig, weil man eben auf synchronisierte Zugriffe achten muss und was dazu führt, das einzelne Threads mehr schlafen, als etwas zu tun.

[Kinman]

Jop, denk ich mir ;)
Wär mal lustig einen passenden Multithread Algo zu entwickeln :D

mfg Kinman

[Senior Sanchez]

Jop, denk ich mir ;)
Wär mal lustig einen passenden Multithread Algo zu entwickeln :D

mfg Kinman

Hier mal mein gehackter, man beachte die unschönen synchronized blöcke ;)


public class Prim {

private final boolean[] zahlen = new boolean[10000000];
private final double len1 = Math.sqrt(zahlen.length);
private final int len = zahlen.length;
private static long time1 = 0;
private long time2 = 0;
//hier kann die Anzahl der Threads bestimmt werden, eventuell auch über args bei main()
private final int THREADCOUNT = 2;
//2 ist die Startzahl, ab dieser wird überprüft was eine Primzahl ist und was nicht
private int currentNumber = 1;
private final Object lock = new Object();
private final Object lock2 = new Object();
private int counter = 0;

public Prim() {
this.berechnePrim();
}

private void berechnePrim() {
//erzeuge die primthreads
int a = 0;
while(a < THREADCOUNT) {
new PrimThread().start();
a++;
}

}

private class PrimThread extends Thread {

int zahl = currentNumber;

public void run() {
int b= 0;
while(zahl < len1) {

synchronized (lock) {
zahl = ++currentNumber;
}

if (!zahlen[zahl]) {
int a = 2;
while((b = a * zahl) < len) {
if(!zahlen[b]) {
zahlen[b] = true;
}
a++;
}
}

}

synchronized(lock2) {
counter++;
}

//Ausgabe
if(counter == THREADCOUNT) {
time2 = System.currentTimeMillis();

System.out.println(time2 - time1);

counter = 0;
//ausgeben aller primzahlen
for(int i=1, len = zahlen.length; i < len; i++) {
if(zahlen[i] == false) {
counter++;
}
}

System.out.println(counter);
}
}

}

public static void main(String[] args) {
Prim.time1 = System.currentTimeMillis();
new Prim();
}

}

[Kinman]

Jo, ein bisschen schneller wirds schon sein, aber nicht allzuviel...
Ich werd mir mal in einer langweiligen (Schul-)Stunde mir überlegen, wie man das ganze eventuell Multithreaded lösen kann, dass es auch wirklich viel bringt.

mfg Kinman

[Senior Sanchez]

Jo, ein bisschen schneller wirds schon sein, aber nicht allzuviel...
Ich werd mir mal in einer langweiligen (Schul-)Stunde mir überlegen, wie man das ganze eventuell Multithreaded lösen kann, dass es auch wirklich viel bringt.

mfg Kinman

Ich habs mal gerade schnell Durchgemessen: Für das Finden aller Primzahlen von 1 bis 10 Mio braucht mein Athlon XP 1800+ mit 1.5er JDK und 2 Threads etwa 0,9s.

[Uni]

so. danke für den tipp mit der "25". ich hab das prog erweitert, dass nu 25 keine primzahl is.

ich hab leider vergessen zu erwähnen, dass ich erst seit einer woche programmiere. daher sin meine möglichkeiten etwas beschränkt.

die wikipedia-seite is sehr interessant, danke

[Senior Sanchez]

so. danke für den tipp mit der "25". ich hab das prog erweitert, dass nu 25 keine primzahl is.

ich hab leider vergessen zu erwähnen, dass ich erst seit einer woche programmiere. daher sin meine möglichkeiten etwas beschränkt.

die wikipedia-seite is sehr interessant, danke

Könnteste mal deinen neuen Quelltext zeigen? Dann können wir nochmal drüber guggen.

Die einfachste Variante ist so, wie ich es geposted hatte, damit gehts halt auf jeden Fall.

[Uni]

class Prim
{
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
int a;
int b;
int c;
int d;

a=n%2;
b=n%3;
c=n%5;
d=n%7;

if((a>0)&&(b>0)&&(c>0)&&(d>0))
{
System.out.printf("%d ist eine Primzahl",n);
}
if((n==3)^(n==5)^(n==7))
{
System.out.printf("%d ist eine Primzahl", n);
}
else
{
System.out.printf("%d ist keine Primzahl",n);
}
}
}


wie gesagt: hab das ganze erst seit ner woche (studiere wirt.info). wir ham noch nich so viel gemacht.


if((n==3)^(n==5)^(n==7))
{
System.out.printf("%d ist eine Primzahl", n);
}
else
{
System.out.printf("%d ist keine Primzahl",n);
}

wenn ich den teil anders/besser ausdrücken könnte, dann wär das besser. wir ham die anweisung, dass wir keine befehle nutzen dürfen, die wir noch nich kennen. "else","==" und "^" hatten wir noch nich genauso wie ""%d",n". aber leider fällt mir nix anderes ein.

[Senior Sanchez]

wie gesagt: hab das ganze erst seit ner woche (studiere wirt.info). wir ham noch nich so viel gemacht.


wenn ich den teil anders/besser ausdrücken könnte, dann wär das besser. wir ham die anweisung, dass wir keine befehle nutzen dürfen, die wir noch nich kennen. "else","==" und "^" hatten wir noch nich genauso wie ""%d",n". aber leider fällt mir nix anderes ein.

Der Algorithmus ist wieder fehlerhaft.
Alle Zahlen bei der jeder Primfaktor größer als 7 ist, z.B. bei 143 (= 11 * 13) werden deine Algo zum stolpern bringen. Du brauchst wohl oder übel ne Schleife.
Kommste mit meinem zuerst geposteten Source klar? Hattet ihr schon Schleifen?

EDIT: Nimm doch z.B. System.out.println(n + " ist eine Primzahl");
*dich beneid, weil du schon studieren kannst :usad:*

[ethrandil]

Also grundsätzlich kannst du nicht ohne weiteres spezielle Faktoren auschließen, sondern musst alle testen. Die einfachste Form wäre so:

n = zu testende zahl
b = 2
solange b < wurzel(n) mach:
falls n teilbar b sag "n nicht prim!"
sonst b = b+1

nach der Schleife bist du sicher, dass n eine Primzahl ist.

Ansonsten was Vernünftiges in Scheme
(define (miller-once t u n a)
(define (_quad-mod-n x) ; x^2 mod n
(modulo (expt x 2) n))
(define (_loop t temp prevtemp)
(cond
[(= t 0) (= 1 (modulo (expt a (sub1 n)) n))] ; a^(n-1) mod n != 1
[(and (= temp 1) (not (= prevtemp 1)) (not (= prevtemp (sub1 n)))) false] ; nicht-triviale wurzel gefunden
[else (_loop (sub1 t) (_quad-mod-n temp) temp)])) ; suche weiter nach nicht-trivialer wurzel
(define _expt-mod-aun ; (a^u mod n)^2 mod n
(_quad-mod-n (modulo (expt a u) n)))

(_loop (sub1 t) _expt-mod-aun _expt-mod-aun))

(define (calc-t-u ns1 t) ; finde a^t * u = n-1 = ns1
(cond
[(= (modulo ns1 2) 0) (calc-t-u (/ ns1 2) (add1 t))]
[else (list t ns1)]))

(define (miller-once-full n a)
(define _t-u (calc-t-u (sub1 n) 0))
(miller-once (car _t-u) (cadr _t-u) n a))

(define (miller-rabbin-prim? n)
(define (_miller n t)
(cond
[(= t 0) (miller-once-full n (add1 (random (- n 1))))]
[(miller-once-full n (add1 (random (- n 1)))) (_miller n (sub1 t))]
[else false]))
(cond [(<= n 1) false]
[(= n 2) true]
[(= (modulo n 2) 0) false]
[else (_miller n 16)]))

(miller-rabbin-prim? 1096)
(miller-rabbin-prim? 1097)
srykthx :rolleyes: :ugly2:

- Eth

[Uni]

class Prim
{
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
int a;
int b;
int c;
int d;

a=n%2;
b=n%3;
c=n%5;
d=n%7;

if((a>0)&&(b>0)&&(c>0)&&(d>0))
{
System.out.printf("%d ist eine Primzahl",n);
}


ich darf nur die befehle nehmen, die ich hier benutzt hab. das is ja grad das schwierige dran ;(

@sanchez:


int n=Integer.parseInt(args[0]);
int a=2;
int b;

b=n%a;

while(n>=a)
{
a=a+1;
}
if(b=0)
System.out.println("n ist eine Primzahl");

so.. nu is der code von meinen verboten her in ordnung. leider findet man damit keine primzahl über 100 :)
laut meinem prog is 143 keine primzahl :)
der code schaut für mich logisch aus, aber leider: ich darf kein != oda break benutzen.
je länger ich mich mit dem prog geschäftige, desto besser lösungen find ich. aber ich kann sie nich benutzen, da ich die nötigen befehle nich anwenden darf :mad:

[Controller Khan]

bei mir sind im Vorkurs in der ersten Stunde schon Schleifen behandelt worden.
Die Vorlesung über Java hat gleich darauf aufgebaut (Info).

thnx für http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

ich habe ebenfalls nach den Namen davon gesucht.

[Uni]

genau nach dem sieb arbeitet ja mein programm.

hier die ein neuer versuch

int n=Integer.parseInt(args[0]);
int a=2;
int b;

b=n%a;

while(n>=a)
{
a=a+1;
}
if(b>0)
System.out.println("n ist eine Primzahl");

leider gibts so keine primzahlen über 100.

[Senior Sanchez]

genau nach dem sieb arbeitet ja mein programm.

hier die ein neuer versuch

leider gibts so keine primzahlen über 100.

deine Schleife ist irgendwie sinnlos.
Sie macht nichts weiteres als a zu inkrementieren, aber du benutzt a danach überhaupt net mehr.
Außerdem prüfst du nur auf rest-Teilbarkeit der Zahl mit 2, sprich, bei dir ist es so, wenn ich 9 per modulo-Operation durch 2 teile, entsteht ein Rest und 9 wird als Primzahl bezeichnet. Dabei stimmt das wohl nicht so ganz, denn 9 = 3 * 3 ;)

EDIT: Außerdem arbeitet dein programm nicht nach dem Sieb.

Hier mal korrigiert, so müsste es gehen, auch wenn der code nich schön ist. Der ist sogar ganz doll unschön und ich habe ihn jetzt mal notdürftig geflickt, das er halbwegs funktionieren sollte. Halte dich lieber an meine Vorgabe und ändere das deinem kenntnisstand oder das was ihr verwendet dürft, ab.

int n=Integer.parseInt(args[0]);
int a=2;
int b;

if(n == 1) {
System.out.println("n ist keine Primzahl");
}

while(n>=a)
{
b=n%a;
if(b > 0) {
a = n+1;
}
a=a+1;

}
if(b>0)
System.out.println("n ist eine Primzahl");

[Uni]

ja, nu arbeitet es nich mehr nach dem sieb. aber die ersten "versionen" waren das sieb. nur rückwerts.

[Uni]

b soll nich initialisiert sein :(..gut das ich noch 2 wochen bis zu abgabe hab.

[Senior Sanchez]

b soll nich initialisiert sein :(..gut das ich noch 2 wochen bis zu abgabe hab.

Zähle mal auf was du nun verwenden darfst und was nicht.
Im grunde ist es bloß ne Schleife, die alle Zahlen kleiner gleich der zu testenden Zahlen als Divisor verwendet und in jedem Schritt auf restlose Teilbarkeit prüft. kannst natürlich auch prüfen ob irgendwann mal nen rest entsteht und dann ne ausgabe machen, aber die aufgabe finde ich nun nicht so schwer, zumal schon zig Mal die Lösung erläutert wurde.

[Uni]

stimmt schon. von der logik is die aufgabe pillepalle. leider hab ich sehr beschränkt kenntnisse und möglichkeiten. in 2 jahren rotz ich hoffentlich sowas hin, nur jetzt isses noch etwas schwer meine gedanken so zu formulieren, dasses java auch so versteht, wie ich das will.

sachen die ich "kenne"
=,&&,%, "normale" rechenoperatoren
if, while

das is alles. zumindest was rechenrelevant is.
is wirklich erschreckend wenig

[Kinman]

damit kann man es eh schon notdürftig hinflicken....

Folgendes ist nur Pseudocode:


int zahl = xxxx; //Die Zahl, die überprüft werden soll
int a = 1; //Teiler
boolean bRun = true; //Dein selbstgebautes break
boolean isPrime = true;

while(bRun == true)
{
if (a < zahl - 1)
{
a++;
}
else
{
bRun = false;
}

if (zahl % a == 0)
{
isPrime = false;
bRun = false;
}
}
//jetzt steht in der isPrime drin ob es sich um eine Primzahl handelt oder net...


Hoffentlich hab ich da jetzt nix falsch gemacht, weil getestet hab ichs net.

mfg Kinman

EDIT: Was ist denn das für eine dämliche Regel: "Neues lernen verboten"

[KhanRKerensky]

Ich würde die Schleife ja anders konstruieren.

while( (a++ < zahl - 1) && isPrime )
{
if (zahl % a == 0)
{
isPrime = false;
}
}

Theoretisch kann man das sogar noch vereinfachen.

while( (a++ < zahl - 1) && isPrime )
{
isPrime = zahl % a;
}

Wodurch wir zu

while( (a++ < zahl - 1) && (isPrime = zahl % a) );

kommen, was sich zumindest unter C so compilen ließe (auch wenns nicht ganz so hübsch ist).
Ich kenn zwar Java nicht wirklich aber ich schätze das ließe sich auch dort ähnlich umsetzen. Je nach dem wie ein boolean in Java definiert ist muss man den "(isPrime = zahl % a)" Teil in "(isPrime = (zahl % a == 0))" ändern.

[Uni]

die codes sin alle nich schlecht. nur darf ich sie nich benutzen. unser prof is da etwas sehr eigen.

[Kinman]

warum darfst du sie nicht nutzen? ich habe nur dinge verwendet, die du oben angeführt hast.

mfg Kinman

[Uni]

boolean bRun = true; //Dein selbstgebautes break
boolean isPrime = true;

while(bRun == true)


boolean is nich. true auch nich. else darf ich auch nich benutzen. so langsam nervts mich. es gibt 100 möglickeiten, aber ich darf keine hernehmen, weil der prof will, dass nur mit den befehler proggen, die er uns gesagt hab.

[Kinman]

int zahl = xxxx; //Die Zahl, die überprüft werden soll
int a = 1; //Teiler
int bRun = 1; //Dein selbstgebautes break
int isPrime = 1;

while(bRun == 1)
{
if (a < zahl - 1)
{
a++;
}

if (a >= zahl - 1)
{
bRun = 0;
}

if (zahl % a == 0)
{
isPrime = 0;
bRun = 0;
}
}
//jetzt steht in der isPrime drin ob es sich um eine Primzahl handelt oder net...


ohne bool, ohne else

[Coda]

Kein boolean und kein else, ist der etwas masochistisch veranlagt?

[Uni]

das denk ich mir auch immer..
thx für den code. der sieht richtig "gut" aus.

[Kinman]

mach das prgramm 2mal.
1mal so wie ihr es müsst und einmal machs mit dem Sieb des Eratosthenes Prinzip.

Hier der C++ Code:


#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
bool a[1000000];
int i, j, number = 999999;

for (i = 0; i < number; i++)
{
a[i] = 1;
}

for (i = 2; i < number; i++)
{
if (a[i] == 1)
{
for(j = i; j < number; j++)
{
if (i * j <= number)
{
a[i * j] = 0;
}
}
}
}

for (i = 1; i < number; i++)
{
if (a[i] == 1)
{
printf("%d\n", i);
}
}
return 0;
}


mfg Kinman

[Uni]

class Prim
{
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
int d = 2

while((n%d!=0)&&(d<n))
{
d=d+1;
}
if(n==d)
System.out.printf("%d ist eine Primzahl", n);
if(n!=d)
System.out.printf("%d ist keine Primzahl", n);
}
}


so.. das is meine finale lösung.. wenn sich jemand wundert warum "!=" und "==" vorkommen: der dozent hat uns heute "erlaubt" die operatoren anzuwenden :D