Primzahl

braco91

Hallo,

ich möchte gerne überprüfen, ob eine eingegebene ganze Zahl eine Primzahl ist oder nicht.

, d.h. lese ich in einer funktion eine zahl ein, typ long, returne sie und rufe mit einer anderen funktion eine Primzahlenkontrolle auf die wie folgt ausschaut:

long func_primtest(long zahl)
{
    int teiler;
    long ergebnis;
    for(teiler=2;teiler<=(zahl-1);teiler++)
    {
        ergebnis=zahl%teiler;

        if(ergebnis == 0)
        {
            printf("Keine Primzahl!\n");
            break;
        }
        else if(ergebnis != 0)
        {
            printf("Primzahl!\n");
            break;
        }
    }
    return 0;
}

die for schleife zählt von 2 bis zahl-1 hoch, wenn in diesem bereich eine zahl durch den teiler (zähler) teilbar ist, dann gib keine primzahl aus; ansonsten also wenn die zahl durch keinen wert in diesem bereich teilbar ist, dann gib:Primzahl aus.

irgendwas funktioniert aber nicht wirklich, weil ich immer "keine primzahl" bekommt, jemand eine idee? (bin noch nicht so weit!)

icarus2

Hast du schon einmal geschaut wie oft die Schleife durchlaufen wird?
Genau ein einziges mal, denn entweder if(ergebnis == 0) oder else if(ergebnis != 0) ist immer erfuellt. Das heisst nach einem Durchlauf der Schleife wird immer abgebrochen.

Das musst du anders loesen.

icarus2

Das ganze koennte zum Beispiel so aussehen:

void prime_test(const long number) 
{ 
	long factor;
    int is_composite = 0;

	for ( factor = 2; factor < number; ++factor )
	{
		if ( number % factor == 0 )
		{
			is_composite = 1;
			break;
		}
	}

	if ( is_composite || number <= 1 )
		printf("%s\n", "No prime number");
	else
		printf("%s\n", "Prime number");
}

Ich denke der Code duerfte klar sein.

Mit ein paar einfachen Tricks kannst du den Code noch etwas optimieren.

In der for-Schleife kannst du folgende Abbruchbedingung waehlen:

factor < sqrt(number)

Wieso man das so machen kann sieht man schnell wenn man etwas darueber nachdenkt.

Du koenntest von Anfang an ueberpruefen, ob 'number' gerade ist. Wenn ja kann es keine Primzahl sein, ausser number ist 2. Dann kannst du als Faktoren nur noch ungerade Werte betrachten. Du kannst die Anzahl Schleifendurchlaufe also in etwa halbieren.

braco91

oh man, typischer anfängerfehler, zwei ifs die die schleife sofort beenden

hab es jetzt raus, vielen dank

Wie soll denn bei deinem else etwas anderes rauskommen als ergebnis != 0 ?
Da brauchst du kein if mehr im else-Zweig.