Primzahltest

[Schrubber]

Hallo Leute

Ich bins mal wieder, der nervige Schrubber ^^


Mein heutiges Problem ist folgendes:


Ich will, dass de Benutzer eine Zahl eingeben kann. Diese soll dann überprüft werden, ob sie eine Primzahl ist.

import java.io.*;

public class Primzahltest 
{
	public static void main(String[] args)
	  throws IOException
	  {
	      BufferedReader in = new BufferedReader(
	              new InputStreamReader(System.in));
		System.out.println("Funktionsweise:");
		System.out.println("Das Programm rechnet alle Zahlen von 2 - Variable-Primzahl als Division und schaut,");
		System.out.println("ob ein Rest besteht. Falls ja, ist es eine Primzahl.");
		System.out.println("Falls nein, ist es KEINE Primzahl.");
		System.out.println("");
	      System.out.println("Bitte Zahl eingeben.");
		  	String input = in.readLine();
		  	int primzahleingabe = Integer.parseInt(input);
		  	System.out.println("Die eingegebene Zahl ist "+primzahleingabe+".");
		  	int i = 2;
		  	int prime=0;
	        if (primzahleingabe < 2) 
	        {
	        	System.out.println("Die Zahl ist keine Primzahl.");
	        } 
			else
	        {
	            while (i < primzahleingabe)
	            {
	            	i = i + 1;
	            	if (primzahleingabe % i != 0)
	            	{
	            		prime = 1337;
	            	}
	            	if (primzahleingabe % i == 0)
	            	{
	            		prime = 666;
	            	}
	            	}
	            	
	                }
if(prime == 1337)
{
System.out.println("Die eingegebene Zahl ist eine Primzahl.");
}
if(prime == 666)
{
System.out.println("Die eingegebene Zahl ist keine Primzahl.");
}
	            }
	  }

Aber das funktioniert irgendwie nicht. Er gibt mir bei Zahlen, die 100% KEINE Primzahlen sind (8,12), die Meldung aus. Woran kann das liegen?



Schrubber

 

[faetzminator]

Die Diskussion über die verschiedenen Algo und Beschrieb des einfachsten Algos (es muss immer noch nicht 2-n sondern 2-n^0.5 getestet werden) gibt es bereits genügend Topics, z.B. hier: http://www.java-forum.org/mathematik/88011-primzahlen-berechnung.html

 

[Leroy42]

Was ist das denn für ein merkwürdiger Primzahltest-Algorithmus? ???:L

Du kannst/mußt deine Testschleife abbrechen sobald du einen
Teiler gefunden hast und in diesem Fall den Kandidaten als nicht prim
erkennen; Falls es keinen solchen Teiler gibt, ist der Kandidat eine Primzahl.

Außerdem sind deine Flags 666 und 1337 schon recht eigenwillig. :shock:

Warum benutzt du nicht einfach einen boolean

boolean istPrim = ...

 

[faetzminator]

Wie wärs mit:

public static boolean isPrime(int value) {
	value = Math.abs(value);
	if (value < 2) {
		return false;
	}
	int sqrt = (int) Math.sqrt(value);
	for (int i = 2; i <= sqrt; i++) {
		if (value % i == 0) {
			return false;
		}
	}
	return true;
}

Abgesehen davon ist 1337 keine Primzahl.

Edit:
Die längere, unschönere, aber schnellere Methode wäre folgende (Immer noch der gleiche, primitive Algo):

public static boolean isPrime(int value) {
	value = Math.abs(value);
	if (value < 2) {
		return false;
	}
	if (value == 2) {
		return true;
	}
	if (value % 2 == 0) {
		return false;
	}
	int sqrt = (int) Math.sqrt(value);
	for (int i = 3; i <= sqrt; i += 2) {
		if (value % i == 0) {
			return false;
		}
	}
	return true;
}