C++ ~ Primzahlen ...

Man gebe in Google den Begriff "Sieb des Eratosthenes" ein, verknüpft mit dem Begriff "c++" und voila, schon gibts sourcen über sourcen *gg*
MFG

Ecraft

Code:

#include <stdio.h>

void main(void)
{

	char primzahl[100];
	int zahlen[100];

	int i1,i2,ist_primzahl;
	char W=1,F=0;

	for(i1=0;i1<=99;i1++) 

	{
		zahlen[i1] = i1;
	
		ist_primzahl = W; 	
		if (i1==1) ist_primzahl=F; 
	

		for(i2=2;i2<i1;i2++) 	
		{
			if ((i1/i2)*i2==i1) ist_primzahl=F; 
		} 

		if (ist_primzahl==W)
		primzahl[i1] = "*";
		else
		primzahl[i1] = " ";
	
	} 
}

hmm .. ich denk mal der will einfach alle Zahlen von 1-100 auf Primzahlen überprüfen und wenn es eine ist mit dem Vorzeichen "*" signieren ...
Ich hoff mal ich hab da keine Fehler oben eingebaut, hab leider keinen Compiler zur Hand. Du kannst die beiden Arrays danach einfach mit einer Schleife über die selben Indizes ausgeben ...

NG Vivo

@Atrox
Das mit dem arrray als rückgabewert hab ich net bedacht aber ich bin net gerade sattelfest in c . Auf das main hab ich ehrlichgesagt net gschaut. Hätte es vielleicht umbennen sollen. Bringt denn das was das main mit int rückgabewert zu definieren wenn man nix zurückgibt ??

Mit mod schaut das ganze schon viel schöner aus.

Frage in c kann man einfach ein offensichtlich nicht immer int ergebnis von sqrt in einen int haun? (Jetzt oute ich wahrscheinlich grad als ärgerer n00b )

zuerst hatte ich sqrt() in der bedingung drinstehen, aber dann wird es jedesmal neu berechnet und das ist verschwendung. gerade bei typenumwandlungen ist C sehr offen und lasch. allerdings gilt zu beachten:

Code:

int a=4,b=20,s;

a<sqrt(b)   -> true

s=sqrt(b);
a<s         -> false

warum?
beim ersten beispiel: nicht sqrt() wird nach int konvertiert und dann mit a verglichen, sondern a wird zu double konvertiert und dann wird verglichen.

als faustregel gilt, C konvertiert den "kleineren" der beide datentypen einer expression zum größeren.

also, ich kann dir zwar nicht genau sagen, wie es geproggt wird, weil ich c nicht kann, aber so ungefähr kann ich dir eine optimierte lösung geben, hab mir das alles mal überlegt:

wenn man genau nachdenkt, dann muss man eine zahl (zb 50) immer nur durch alle primzahlen, die darunter liegen dividieren, um zu überprüfen, ob die aktuelle eine eben solche ist - denn 1,2,3 sind ja bekanntlich primzahlen, so geht das natürlich ohne array garnet - deswegen schätz ich mal, das war die aufgabe
(ich schreibs dir mal in php hin, weil ich c net kann, vielleicht kanns dir wer 'übersetzen' - sollte aber ähnlich sein)

Code: PHP

function primes($lenght)
{
	$primeValues = array(2);
	echo '1 *<BR>2 *';
	if($lenght<3)
	{
		exit;
	}
	for($i = 3;$i<=$lenght;$i++)
	{
		echo '<BR>'.$i;
		foreach($primeValues as $dummy)
		{
			if(intval($i/$dummy)*$dummy==$i)
			{
				$is_prime = FALSE;
				break 1;
			}
			else
			{
				$is_prime = TRUE;
			}
		}
		if($is_prime==TRUE)
		{
			array_push($primeValues,$i);
			echo ' *';
		}
	}
}

zu beachten ist, dass 1 und 2 zwar primzahlen sind, aber eine 'besondere' bedeutung haben, und für die berechnung der zwei die funktion ca doppelt so lange und ca 4mal langsamer wäre...

ps: grad gesehen - beim atrox unten wird 1 und 2 auch ignoriert

pps: @crash: und manchmal nerven solche automatischen sachen auch gewaltig...

achja © by watchout

Zitat von Vivo

Das Prob is in C kannst nicht so einfach die Charakters mit ints vermischen...
Die Syntax von PHP is zwar ähnlich, aber sachen wie foreach und array_push muss man alles selbst ausproggen ...

also, das einzige mal, wo characters mit ints vermischt werden, is beim echo und ich dort nur wegen dem <BR>, welches ja im c nicht notwendig ist

array_push kann man durch definition eines array[length] vermeiden (das geht in php net...ausser im nachhinein mit array_pad, wodurch sichs nimmer auszahlt )
foreach ^= for(k=1,k<=dim(array),k++)

ps: wichtig is vielleicht noch, dass bei meiner lösung im array nur die primzahlen drinnen sind...

Zitat von watchout

wenn man genau nachdenkt, dann muss man eine zahl (zb 50) immer nur durch alle primzahlen, die darunter liegen dividieren, um zu überprüfen,

du hast natürlich recht, man braucht aber gar kein stack oder dynamisches array, es steht ja schon alles im ergebnis-array:

Code:

#include <stdlib.h>
#include <stdio.h>
#define n 100

int main() {
  int e[n]={1,2};
  int ei=2,i1,i2,s;
  for (i1=3;i1<n;i1++) {
    for (i2=1;i2<ei&&i1%e[i2];i2++);
    if (i2>=ei) e[ei++]=i1;
  }
  for (i1=1,i2=0;i2<ei && i1<n;i1++)
    if (e[i2]>i1) printf("* "); else {printf("%d ",i1); i2++;}
  return 0;
}

Zitat von atrox

zuerst hatte ich sqrt() in der bedingung drinstehen, aber dann wird es jedesmal neu berechnet und das ist verschwendung. gerade bei typenumwandlungen ist C sehr offen und lasch.

Aber trotzdem wohldefiniert. Bei Konversion von double -> int ist z.B. ganz klar, dass abgerundet werden muss.