Anfänger braucht hilfe

[BeginnerMB]

hallo zusammen,

ich habe vor kurzem begonnen mit C zu programmieren,

dabei bin ich auf folgende aufgabe gestossen !

Man soll feststellen ob eine eingegebene zahl eine Primzahl ist oder nicht ?

ich bin allerdings nicht fähig die aufgabe zu lösen, und brauche hilfe!

 

[Fabian H]

Ich versuchs mal (hab auch kaum Erfahtrung in C)

#include <stdio.h>

int main(int argc, char *argv[])
{
  int i;
  int iZahl    = 123;
  int iIsPrime = 1;
  int iDivide  = 0;

  for( i = 2; i < iZahl; i = i + 1) {
    if (iZahl % i == 0) {
      iDivide  = i;
      iIsPrime = 0;
    }
  }

  if (iIsPrime == 0) {
    printf("%i ist eine Primzahl\nSie ist mindestens durch %i teilbar", iZahl, iDivide);
  } else {
    printf("%i ist keine Primzahl", iZahl);
  }

  return 0;
}

//Edit: bitte das nächste mal ein gescheites Topic wählen (soll ein freundlicher Hinweis sein )

//Edit: so, mal den Denkfehler beseitigt

 

[Harrier]

da ich die oben angegeben lösung noch nciht ganz verstehe versuch eich auch mal eine - hab aber auch noch kaum ahnung von c/c++

#include <stdio.h>

void main() {

int a=8; //deine zahl - könnte nat. auch von woanders her übergeben worden sein

for(i=2;i<8;i++) {
double erg=a/i;
if(erg==2) //weil 2 muss ja wenn es eine prim ist in jedem fall mal kommen)
{ printf ("%a ist eine Prinmzahl!", a); int prim=1; }//sry wenn hier n fehler ist! ich mach norm eher c++ und hab kein plan, ob ich 
//einfach iostream nehmen kann und cout machen kann hier
}
if(prim!=1)
{ printf ("%a ist keine Primzahl!", a); }
}

 

[basd]

ein paar Tipps:

- bei der Untersuchung der Zahl musst du nur bis zur Zahl/2 gehen (eigentlich reicht bis Wurzel der Zahl aber die ist schwerer zu berechen)
- ist die Zahl gerade, ist sie keine primzahl , ausser die Zahl ist gleich 2 --> mit Modulo 2 testen ob Zahl gerade und ungleich 2 ( Falls Primzahl : Zahl % 2 == 1), d.h eine schrittweite von 2 in der Schleife reicht aus

die obere Lösung mit dem Double ist zu "riskant"
die Lösung davor ist im Ausgabetext nicht ganz koscha

 

[Moriarty]

Programmcode

Hi Leute, ich hatte letztens mal einen Code gefunden mit dem man auch bei großen Zahlen eine 99,99%ige Aussage darüber bekommt, ob die Zahl Prim ist oder nicht.

Ich habe leider noch keine alzu große Ahnung von C und bei mir läuft das Programm auch nicht korrekt, vielleicht kann da mal jemand in den Code reinsehen und sagen, wo der Fehler liegt?

//Primzahltest nach Rabin-Miller
//Autor: Germanos Efthimiadis
//letzte Änderung: 13.1.1998

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

#define MAXINT 32767
#define MAXLONGINT 42949672951
#define SICHERHEIT 10001	//Anzahl der Tests mit verschiedenen a

//Autor: Bruce Schneier aus Angewandte Kryptografie S.285
//Funktion: mod
//Aufgabe: Berechnung der funktion modulo
//Parameter: unsigned long int a,x,n
//Rückgabe: unsigned long int (a^x mod n)
unsigned long int mod(unsigned long int a,unsigned long int x,unsigned long int n)
{
	unsigned long int s,t,u;

	s=1;
	t=a;
	u=x;

	while(u)
	{
		if(u&1)
			s=(s*t)%n;
		u>>=1;
		t=(t*t)%n;
	}
	return(s);
}

//Autor: Germnos Efthimiadis
//Funktion: Zufall
//Aufgabe: Berechnung einer zufallszahl<Obergrenze
//Parameter: unsigned long int i
//Rückgabe: unsigned long int (Zufallszahl)
unsigned long int Zufall(unsigned long int i)
{
	unsigned long int x,x1,x2,x3;
	x1=(unsigned long int)random(MAXINT);
	x2=(unsigned long int)random(MAXINT);
	x3=(unsigned long int)ramdom(MAXINT);
	x=x1*x2*x3;
	x%=i;	//x<i;
	return(x);
}

//Autor: Germanos Efthimiadis
//Funktion: Hauptprogramm
//Aufgabe: Primzahltest nach Rabin Miller
//Parameter: keine
//Rückgabe: keine
void main (void)
{
	unsigned long int k,y,b,m,j,z;

	//In diesem Array werden alle a's gespeichert
	//So wird verhindert, dass man mit demselben a nochmal prüft
	unsigned long int a[SICHERHEIT];
	unsigned long int p;
	int CursorY,CursorX;	//Cursokoordinaten

	randomize();	//Initialisierung des Z-Generators

	printf("\n\nEs wird eine ungerade Zufallszahl p erzeugt");
	p=Zufall(MAXLONGINT);
	if (p%2==0)
		p--;	//Ungerade Zahl
	if (p<10000000001)
		p+=10000000001;	//10-stellige Zahl
	printf("\np=%lu\n",p);
	printf("\np wird jetzt %lu mal getestet\n",SICHERHEIT);

	b=0;	// Wie oft lässt sich p-1 ohne Rest teilen?
	m=p-1;
	while (m%2==0)
	{
		m/=2;
		b++;
	};	//m ergibt sich aus der Berechnung von b

	CursorX=wherex();
	CursorY=wherey();
	for (k=0;k<SICHERHEIT;k++)
	{
		gotoxy(CursorX,CursorY);
		printf("%lu. Test",k+1);
		//Schritt 1
		a[k]=Zufall(p-2);
		y=0;
		while (y<k)
		{
			if (a[k]==a[y])	//Gibt's die Zahl schon?
			{
				a[k]=Zufall(p-2);	//Erzeuge neue Zahl
				y=0;	//Beginne Vergleich von vorne
			} else
				y++;	//Setze Vergleich fort
		}

		//Schritt 2
		j=0;
		z=mod(a[k],m,p);

		//Schritt 3
		if (!(z==1 || z==p-1))
			goto keine_primzahl;

		//Schritt 4
schritt4:
		if (j>0 && z==1)
			goto keine_primzahl;

		//Schritt 5
		j++;
		if (j<b && z!=p-1)
		{
			z=mod(z,2,p);
			goto schritt4;
		}

		if (z!=p-1)
			goto keine_primzahl;

		//Schritt 6
		if (j!=b || z==p-1)
		{
			printf("\n%lu ist eine Primzahl",p);
			return;
		}
keine_primzahl:
		printf("\n%lu ist keine Primzahl",p);
		return;
	}
}

Den Text dazu habe ich auf der Seite: FH Esslingen, Hochschule für Technik

Ich werde auch die Datei mit dem Scourcecode anhängen, damit man sie leichter downloaden kann.