Primzahlen in C

Hallo zusammen,

ich habe die Aufgabe auf ein C-Programm zu schreiben dass alle Primzahlen bis zur Eingegebenen Zahl ausgibt. Den Teil ob eine Zahl eine Primzahl ist funktioniert. Und dachte ich pack einfach ne schleife drum die mir die Variable hoch-zählt. Nur irgendwie mach ich ein Fehler und kapier nicht warum xD

Könnt ihr mir helfen ?

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

int main(void){

	unsigned int iZ,i,a, iA;
	unsigned short suiResult = 0;

	printf("Bitte geben Sie eine Zahl ein  ");
	scanf("%d",&iA);

	for(a = 0;a < iA ;a++){

		iZ = a;

		for (i = 2; (i < iZ) && (suiResult == 0); i++)  //funktioniert
		{
			if (iZ % i == 0)
			{
				suiResult = 1;	
			}
		}

		if (suiResult == 0)
		{
		   printf("\n%d ist eine Primzahl", iZ);
		}
		else
		{
		   printf("\n%d ist keine Primzahl", iZ);
		}
	}

	_getch();

	return EXIT_SUCCESS;

}

int primer(unsigned int iA){

    unsigned int iZ,i,a;
    unsigned short suiResult = 0;
	printf("\n0 ist keine Primzahl");
	printf("\n1 ist keine Primzahl");
    for(a = 2;a < iA ;a++){

        iZ = a;
		suiResult = 0;
        for (i = 2; (i < iZ) && (suiResult == 0); i++)  //funktioniert
        {
            if (iZ % i == 0)
            {
                suiResult = 1;
            }
        }

        if (suiResult == 0)
        {
           printf("\n%d ist eine Primzahl", iZ);
        }
        else
        {
           printf("\n%d ist keine Primzahl", iZ);
        }
    }

    return EXIT_SUCCESS;

}

suiResult musst du natürlich immer wieder zurücksetzen und 0 und 1 sind keine.

Wutz

gerrelic schrieb:

Nur irgendwie mach ich ein Fehler und kapier nicht warum

Sollen wir jetzt hier anhand des deine Codes rätseln, was DEIN Fehler ist?
Stelle eine konkrete Frage und dazu gehört zu sagen was DEIN Fehler ist.
Vielleicht findet sich ja dann jemand.

Wutz schrieb:

gerrelic schrieb:

Nur irgendwie mach ich ein Fehler und kapier nicht warum

Sollen wir jetzt hier anhand des deine Codes rätseln, was DEIN Fehler ist?
Stelle eine konkrete Frage und dazu gehört zu sagen was DEIN Fehler ist.
Vielleicht findet sich ja dann jemand.

was soll der post auf eine gelöste frage bringen

mussu machen mit sieb of aristoteles

icarus2

ninchen schrieb:

mussu machen mit sieb of aristoteles

Du meinst bestimmt das Sieb des Eratosthenes

für den anfang würde auch eine obere suchgrenze von sqrt(iZ) reichen.

Aristoteles war Philosoph in Reinkultur; das Einzige, was er mit Mathematikern gemeinsam hat, ist, dass ihn die wirkliche Welt nicht sonderlich interessiert hat. (Nichts gegen Mathematik - Mathematiker machen sich über sehr abgehobenes Zeug Gedanken, das sich aber in aller Regel irgendwann als ausgesprochen nützlich herausstellt)

Das Problem mit dem Sieb des Eratosthenes ist, dass es bei großen Bereichen Unmengen Speicher verschlingt. Das Atkin-Sieb ist eine Verbesserung, aber auch komplizierter zu implementieren.

Ich hätte jetzt vorgeschlagen,

1. Faktoren nur bis zur Quadratwurzel der geprüften Zahl zu prüfen,
2. nur jede zweite Zahl zu prüfen, oder auch abwechselnd eine und drei zu überspringen
3. Die bereits gefundenen Primzahlen in einer Liste vorzuhalten und nur Primfaktoren zu prüfen.

Das ist billig zu haben und drückt das Laufzeitverhalten von O(N²) auf O(N * sqrt(N) / ln(sqrt(N))). Wahrscheinlich gibt es noch eine kleinere passende Laufzeitklasse, aber mir fehlt die zahlentheoretische Expertise, abzuschätzen, der wievielte Primfaktor durchschnittlich jeweils eine Zahl zwischen 1 und N teilt. Der Speicherbedarf ist O(sqrt(N) / ln(sqrt(N))), d.h. um alle durch 32 bit darstellbaren Integer zu prüfen, braucht es etwa 24 Kilobyte (und ein paar Stunden Zeit).