C Primfaktorzerlegung und erkennung / zusammenfügen

[ExiizZ]

Hallo,

bin derzeit an einer Übungsaufgabe und komme einfach nichtmehr weiter.
Es geht darum eine Primfaktorzerlegung in C zu programmieren.

Das ist aktuell mein Code

#include <stdio.h>

int main() {
	int z, p=2;
	
scanf("%d", &z);

if ((z== 0) || (z==1)) {

	printf("%d ist prim.\n", z);
}

else {
	

	
	while (z%p!=0)
	{
		p++;
	}		
	while(z%p==0)	
	{
	z=z/p;
	printf("%d\n", p);
 
	while (z%p!=0)
	{
	p++;
	}
}

if (z%p!=0) {
	p++;
	z = z / p;
	printf("%d\n ", p);
	
	p++;
}
}
return 0;
}

Es funktioniert auch alles jedoch kommt es zu einem Fehler. Etwa 1 - 2 Minuten nach der Primfaktorzerlegung im Programm haut er mir unendliche (-1)e raus.

Das nächste Problem ist nun wenn der Anwender eine Primzahl eingibt soll dieser direkt "Prim" ausgeben und nicht den Faktor. Ich hab mir gedacht ich bekomme es hin durch Primfaktorerkennung mit einer for schleife

#include <stdio.h>

int main() {
	int z, p=2;
	
scanf("%d", &z);

if ((z== 0) || (z==1)) {

	printf("%d ist prim.\n", z);
}

else {

        for ( int teiler=2; teiler < z; teiler++) { 
        if( z % teiler == 0) {

                

}
}
printf("Primzahl\n");	
	
}}

Nun habe ich total viele Möglichkeiten schon versucht beide Aufgaben in einen Code zusammenzufügen bekomme jedoch oft Probleme damit...

Hoffe mir kann hier jemand weiterhelfen.

Ergänzung (23. November 2015)

Habe inzwischen mein fehler mit den -1en entdeckt und verbesser ich bräuchte nur noch einen vorschlag zum zusammenfügen

 

[powerfx]

Abgesehen davon, dass weder 0 noch 1 Primzahlen sind, kommst du im else-Zweig ja nicht mehr zu printf mit dem entsprechenden Text. Ansonsten hast du ja in beiden Teilen die gleiche if-Bedingung. Was ist also das genaue Problem?

 

[ExiizZ]

Naja die Sache ist ich möchte dass das Programm erst überprüft ob der Anwender eine Primzahl eingegeben hat, wenn ja dann soll es ausgeben "... in eine Primzahl" wenn er keine Primzahl eingibt soll das Programm die natürliche Zahl in ihre Faktoren zerlegen. Im Prinzip hab ich ja nun beide programme aber weiß nicht wie ich diese verknüpfen soll. Hab es mehrmals versucht aber erfolglos..

Ergänzung (23. November 2015)

So hab es hinbekommen

 

[pfd]

Um zu überprüfen, ob eine Zahl prim ist oder nicht, muss du diese in ihre Faktoren zerlegen. Derzeit führst du diese Zerlegung zweimal durch, einmal zur Überprüfung ob prim oder nicht und einmal um die Faktoren zu berechnen.

Ich würde die Zerlegung nur einmal durchführen und in ein dynamisches Array speichern. Hat das Array nach der Zerlegung die Länge 1, so ist die Zahl eine Primzahl ansonsten gebe das Array am Bildschirm aus.

Und du musst die Zerlegung nur bis sqrt(n), wobei n die zu überprüfende Zahl ist, durchführen. Den Grund kannst du hier nachlesen.

 

[Stannis]

Wie der Zufall es will, habe ich kürzlich das gleiche gemacht und kann vielleicht ein paar zusätzliche Ratschläge geben:

1. Es empfiehlt sich, bis zur eigentlichen Zerlegung die möglichen Primfaktoren zu erstellen. Der kleinste Primfaktor ist 2, daher kann der größte Primfaktor höchstens eingabe/2+1 sein. Bis zu dieser Grenze solltest du Primzahlen erstellen.
2. Das Erstellungsarray kannst du von Anfang an nur mit ungeraden Zahlen füllen und hinterher mit dem Sieb des Eratosthenes durchpflügen.
3. Bei der eigentlichen Primfaktorprüfung kommt man um Modulo nicht herum.

Wenn du die Primzahlen nicht mit modulo, sondern durch das Streichen von Vielfachen im Array herausfindest, erhöht sich die Performance um das hundertfache.

 

[SparkMonkay]

Ich würde es folgendermaßen machen.

Mach dir eine verkettete Liste, welche die Primzahlen die du bisher bestimmt hast enthält.
Lauf von 3 aus jedes 2. Element hoch (damit du nicht durch 2 teilen musst, denn jede 2. Zahl ist ja gerade).

Dann teilst du durch alle Elemente in deiner Liste, und sobald eins nicht passt, dann ist es nicht prim. Also z.B.
zuTestendeZahl modulo primzahl1 == 0
Das ist g.d.w die Zahl kein prim ist, wäre sie prim, würde da anstatt ==, != kommen.

Hoffe ich konnte dir helfen.

Zu dem Aufbau deiner Primzahlen: http://www.c-howto.de/tutorial-strukturierte-datentypen-strukturen-struct.html


Hier mal der Code wie ich den machen würde.

struct primzahlen
{
	int prim = 0; //vorerst mal 0 gesetzt
        struct primzahlenNext = null; //der pointer auf die nächste Primzahl in dieser Liste
                                                   //primPrev kann man man machen ist aber unnötig, da man nie die vorherigen braucht.
};

Grüße Spark

@Schnitzelsemmel
Da ist ein Problem, bei, das ist aufwändiger zu programmieren. Du kannst damit arbeiten zu sagen jede 2. und 3. Zahl überspringe ich, damit betrachtet man mindestens die hälfte der Zahlen nicht, vorallem wenn man nicht "i++" sondern "i=i+2" nutzt, daraus folgt dann eine Performancesteigerung von 50% (ca.) bzw. eigentlicht eine Senkung von 50% der Vergleiche die man sonst machen würde.

 

[daemon777]

Die einfache Probedivision-Methode für eine Zahl n ist wesentlich schneller, als ein Array aller Zahlen 1 bis n, bei dem jeweils jedes Vielfache der aktuellen Zahl herausgestrichen wird. Abgesehen ist der Speicheraufwand jeweils von Gut und Böse.

Alle Primzahlen, die kleiner als Wurzel(n) sind zu testen, mag ja erstmal eine gute Idee sein, aber auch hier ist der Speicheraufwand einfach zu groß. Schon bei relativ kleinen Zahlen fliegt einem das um die Ohren (bzw. ist einfach langsamer als der Trivialansatz).

Ein Performancetip wäre:
Ist n%p gleich 0, dann ist eine mögliche Primfaktorzerleung = p UND Primfaktoren(n/p).
Abgesehen davon, muss man immer nur bis Wurzel(n) checken, da die Zahl n mindestens einen Teiler < Wurzel(n) haben muss, falls sie nicht prim ist.


Wenn man tatsächlich performantere Primzahltests machen möchte, so sollte man sich mal Algorithmen wie den Solovay-Strassen (der Ursprüngliche) oder Miller-Rabin (der schnellere und neuere Algorithmus) anschauen.
Auch zur Primfaktorzerlegung gibt es glaube ich einige Tricks. Die habe ich mir aber bisher leider selbst noch nicht angeschaut.