Primzahlen + extra Bedingung

[Jaipur]

Hi,

ich habe folgendes Problem:

Erstellen Sie ein Programm, das alle Zahlen zwischen 1 und 100000 ausgibt, die nicht durch eine Zahl kleiner als 100 teilbar aber keine Primzahlen sind.

Bei mir gibt es da keine Zahl die ich ausgeben kann .... ist das richtig ?

[hoagi]

Nein das ist falsch

Die kleinste Zahl, die nach der Bedingung dargestellt werden kann ist die Quadratzahl aus der kleinsten Primzahl > 100

Das ist 101.

also 101*101 = 10201 und die ist kleiner als 100000

hoagi

[StefanK]

Hi Jaipur,

wie wärs mit 10201 (nur durch 101 teilbar).

Im Grunde ist die Aufgabe, zuerst alle Primzahlen zwischen 101 und 990 zu suchen und dann alle möglichen Produkte der Zahlen zu errechnen. Dein Ergebnis sind alle Ergebnisse die unter 100000 liegen (das erste habe ich dir oben schon aufgezeigt, das zweite müsste 101*103 sein)

Viel Spass beim Programmieren :WD :WD :WD

[Jaipur]

Hi,

so wie ich die Aufgabe verstehe, dürfen alle Zahlen die ausgegeben werden sollen keine Primzahlen sein und sie dürfen nicht durch eine Zahl teilbar sein die kleiner als 100 ist.

# include <stdio.h>

# include <stdlib.h>


int main()

{

	int i,j,p;


	for( i=100; i<=999; i++)

	{

		for( j=2,p=0; j<i; j++)

			if( (i%j) == 0)

			{

				p=1;

				j=1;

				break;

			}

		if( p == 1)

			if( i*i <= 100000)

				printf("zahl: %d\n",i);

	}


	return 0;

}

Jetzt besser oder liege ich immer noch daneben?

[hoagi]

Nicht ganz, du berücksichst nur Quadratzahlen von Primzahlen.

Es sind aber alle möglichen Kombinationen von Primzahlen zu testen.

Wichtig ist dadurch das 101 der kleinste zulässige Faktor ist

und da 101*101*101 > 100000, du nur Produkte mit 2 Faktoren berücksichtigen mußt.

Ansonsten wäre die Sache etwas komplizierter.

Wichtig falls die Aufgabe erweitert wird und du sagen wir mal Zahlen > 1 000 0000 suchen mußt.

# include <stdio.h>

# include <stdlib.h>


int main()

{

	int i,j;


	for( i=101; i<1000; i+=2)

// Die Variable wird um 2 hochgezählt, weil hier nur ungerade 

// Zahlen vorkommen können.

	{

		if ( ! isprimzahl( i )  )

			continue;

		for( j=101; j<1000; j += 2)

		{

			if ( !isprimzahl(j) )

				continue;

			if( i*i <= 100000 && i >= j)

				printf("zahl: %d\n",i*j);

// Es werden nur Kombinationen zugelassen bei der i >= j

// um doppelte Zahlkombinationen zu vermeiden

		}

	}


	return 0;

}


[/PHP]

[Klotzkopp]

Hier mein Beispiel, ohne Beschränkung auf zwei Faktoren:

#include <stdio.h>


int KleinsterTeiler( int nZahl ) 

{

	int nKT = nZahl;

	for( int i=2; i*i <= nZahl; i++ ) {

		if( 0 == (nZahl % i) ) {

			nKT = i;

			break;

		}

	}


	return nKT;

}


int main()

{

	const int nMax = 100000;

	const int nKleinsterErlaubterTeiler = 100;


	int nStart = nKleinsterErlaubterTeiler * nKleinsterErlaubterTeiler;


	for( int i = nStart; i <= nMax; i++ ) {

		int nKT = KleinsterTeiler( i );

		if( nKT >= nKleinsterErlaubterTeiler && nKT != i ) {

			printf( "%d\n", i );

		}

	}


	return 0;

}

[/PHP]

[Jaipur]

Hi,

@hoagi: Ich war mal so frech und habe Deinen Quellcode durch den Compiler gejagt. Wenn Du in der letzten if-Bedingung noch eine break-Anweisung hineinpackst liefern Unsere Programme "fast" die gleichen Ergebnisse und in der letzten printf-Anweisung habe ich bei dir noch von i*j ein i gemacht.

int isprimzahl( int x)

{

	int i;


	for( i=2; i<x; i++)

		if( (x%i) == 0)

			return 0;

	return 1;

}

Also ich glaube schon fast das meins Richtig ist, die Zahlen dürfen laut Aufgabenstellung keine Primzahlen sein!

Um Antwort wird gebeten ...

[hoagi]

Vielleicht verstehe ich da ja was falsch.

es werden Zahlen gesucht zwischen 1 und 100000.

Ist mir erstemal gar nicht aufgefallen aber dein erstes Programm

wirft nur nicht Primzahlen raus.

Ich glaube du hast da am Anfang was falsch verstanden.

Nicht die Faktoren dürfen keine Primzahlen

(also in deinem Fall i ) sein, sondern das Produkt der ( i*j ) Faktoren in der von StefanK vorgeschlagenen Lösung.

EIne nicht Primzahl zeichet sich dadurch aus, daß sie sich aus zwei Faktoren zusammensetzt.

Die Idee bei der Lösung ist, daß bei der Primzahlenzerlegung keine Zahl < 100 rauskommen darf.

Damit ist klar, daß der kleinste Faktor 101 sein muß.

Da die Zahl < 100000 können aber auch nur zwei Faktoren beteiligt sein ( 101*101*101 > 100000 ).

Somit kann man die ganze Sache von hinten durch die Brust ins Auge lösen.

Nimm alle Zahle zwischen 101 und 999 in allen möglichen Kombinationen, prüfe ob beide Zahlen Primzahlen sind, prüfe ob das Produkt der beiden Zahlen < 100000 und gib dann das Ergebnis raus i*j ( was dann die Zahl 1-100000, die keine Primzahl ist ).

Insgesamt ist die Lösung wirklich nicht besonders geschickt, weil hierbei sehr viele Annahmen über den Wertebereich der Zahlen gemacht werden, und das ganze System kippt , wenn sich der Zahlenbereich ändert.

Ich denke mal die Lösung die Klotzkopf vorschlägt ist die einfachere und auch allgemeingültigere Lösung.

Hoagi

[maxim_42]

@klotzkopp

int KleinsterTeiler( int nZahl )

In der Schleife muss man nZahl nur bis Wurzel nZahl laufen lassen. Weiter optimieren könnte man wenn erst auf Teilbarkeit durch 2 getestet wird, und in der Schleife mit 3 begonnen und jeweils mit 2 inkrementiert wird.

[Klotzkopp]

Original geschrieben von maxim_42

In der Schleife muss man nZahl nur bis Wurzel nZahl laufen lassen.

Und bis wohin läuft meine Schleife?

Was das Optimieren angeht, hast Du natürlich Recht, aber es kam mir auf Verständlichkeit an, nicht auf Laufzeit.

[maxim_42]

habs glatt übersehen!