[C/C++] Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Mr_MeYa · 10. September 2009

Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Mahlzeit,

Wir haben die Aufgabe bekommen, zwischen einem Startwert und einem Endwert die Primzahlen auszugeben. Soweit so gut. Kann man ja alles managen, aber die Problematik ist dabei, das nur for-Schleifen und If-Anwendungen benutzt werden soll.

Ich habe dazu mal das hier geschrieben:

Code:

#include <iostream>
#include <conio.h>
using namespace std;
int main ()
{
 cout << "Dieses Programm gibt ihnen Primzahlen in einem\ndefinierten Bereich aus\n";
 cout << "Bitte geben Sie an, ab welcher Zahl\ndas Programm starten soll\n";
 int anfang;
 cin >> anfang;
 cout << "Nun geben Sie bitte die Zahl an\nbei der das Programm enden soll\n";
 int ende;
 cin >> ende;
 int i;
 int max=1; 
 for(i=anfang;i<=ende;i++)
 {
 switch (i)
 {
 case 1:
 case 2:
 case 3:
 case 5:
 case 7:
 cout << "Bei "<< i <<" ist eine Primzahl\n";
 break;
 default: 
 if ((i%2)!=0 && (i%3)!=0 && (i%4)!=0 && (i%5)!=0 && (i%6)!=0 && (i%7)!=0 && (i%8)!=0 && (i%9)!=0)
 {
 cout << "Bei "<< i <<" ist eine Primzahl\n";
 }
 }
 }
 getch();
}

Nur ist jetzt die Frage, wie bekomm ich das If ein wenig "schöner", ist ja nicht gerade das beste so eine lange Anwendung dareinzubasteln

Das Programm habe ich geschrieben und kompiliert in Dev-C++ 4.9.9.2

Um jede hilfe bedankt sich,
Mr_MeYa

Anzeige

Rushh0ur · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Schöner? ?(
Vielleicht so (1 ist keine Primzahl nach definition: siehe wiki):

Code:

if [COLOR="Red"]([/COLOR] (i==2) || (i==3) || (i==5) || (i==7) || [COLOR="Blue"]([/COLOR] (i!=1) && (i%2) && (i%3) && (i%4) && (i%5) && (i%6) && (i%7) && (i%8) && (i%9) [COLOR="Blue"])[/COLOR] [COLOR="Red"])[/COLOR] { cout << "Bei "<< i <<" ist eine Primzahl\n"; }

Mfg Rushh0ur

Mr_MeYa · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Ja, das ding ist ja doch recht umfangreich, vllt. mit einer 2ten for-Schleife oder ähnlichem?

PS: Danke für den Tipp mit der 1

chrisb · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Ich denke nicht, dass er die Formatierung der Abfrage meint..

Mein Ansatz wäre eher so:

Code:

for (int p = start; p <= end; ++p) {
 bool prime = true;

 for (int i = 2; i <= static_cast<int>(std::sqrt(p) + 1); ++i)
 if (p % i == 0) {
 prime = false;
 break;
 }

 if (prime)
 std::cout << p << " ist Primzahl." << std::endl;
}

Natürlich ist es hier sinnvoller, die innere for-Schleife in eine Funktion auszulagern. Aber ich weiß ja nicht, ob ihr das verwendet dürft. Daher der "Umweg" über das Flag prime.

// Edit: Logische Struktur beibehalten..

// Edit 2: Musst noch auf Sonderfall p=1 aufpassen..

Chillikid · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Ich möchte dich an dieser Stelle noch darauf Hinweisen, dass dein Algorithmus falsch ist.

Um wirklich zu berechnen ob es eine Primzahl ist, bietet sich für deine Anwendung die zwar rechenintensive, aber einfach zu implementierende Probedivision an:
Probedivision – Wikipedia

MfG

Chillikid

Mr_MeYa · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Den Umweg dürfen wir nicht nehmen, sonst wärs ja "einfach" gewesen.

Zu Chillkid:
In dem Wiki-Eintrag steht aber auch:
Für die Probedivision benötigt man eine Liste mit kleinen Primzahlen...

Und die will ich ja haben.

bloodyphoenix · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Naja prnizipiell ist deine Primzahl-Anfrage ja auch irgendwie deppert oder?
ich meine zu schauen ob mod2 mod3 mod4... mod9 ungleich 0 ist ist doch recht , so macht man doch keinen prinzahl-test

ich würde das ganze mit zwei schleifen lösen

Code:

 boolean prim;
for (int i=min;i<max;i++){
prim = true;
for(j=2;j<sqrt(i);j++){ //*
if(i%j==0) { prim=false;}
//evtl noch schleife verlassen
}
if (prim) { cout << i ist Primzahl; } //cout anpassen
}

Da ich keinerlei c++ erfahrungen habe und mein c auch schon nen paar tage her ist, bin ich mir wegen sqrt nicht sicher, soll aber die wurzel sein, denn man muss nur die zahlen 2-sqrt(n) testen, um sagen zu können n ist eine prinzahl oder nicht. desweiteren muss unten das cout noch angepasst werden, die syntax hab ich nciht drauf
€: zu spät =(

Chillikid · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Also für alle Zahlen unter 100 dürfte dein Algorithmus auch stimmen. Aber z.B. 121 lässt sich nicht durch die Zahlen 2-9 Teilen, die du ja abtestest, ist aber trotzdem keine Primzahl.

Mit der kleinen Primzahlliste die man braucht hast du allerdings recht, habe ich nicht dran gedacht. Eine weitere möglichkeit wäre dann noch das Sieb des Eratosthenes, allerdings fängt man da immer bei 2 an, also wieder sehr aufwendig, wenn man z.B. die Primzahlen zwischen 100-200 haben möchte.

chrisb · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

In der Aufgabenstellung steht also explizit, dass du kein zusätzliches Flag verwenden darfst? Das hat ja nichts mit der Einschränkung (nur for-Schleifen und if-Abfragen) zu tun.

Chillikid · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Das ist aber auch kein Primzahlentest. Wieder mein Gegenbeispiel mit 121:

sqrt(121) = 11
2 < 11 --> in 2. Schleife
11%2 = 1 --> prim bleibt true

Es ist aber halt keine Primzahl.

DasBoeseLebt · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Code:

// C++

#include <iostream>

using namespace std;

int main()
{
 
 int anfang = 0, ende = 0;
 const int zwei = 2;
 const int drei = 3;
 const int fuenf = 5;
 const int sieben = 7; 


 do {
 cout <<"Bitte einen Anfangswert eingeben: ";
 cin >> anfang;

 cout << endl;

 cout << "Bitte einen Endwert eingeben: ";
 cin >> ende;

 cout << endl;

 } while(anfang < 0 || ende < 0);


 for (anfang; anfang<ende; anfang++)
 {
 if ((anfang % zwei == 0) && (anfang != 2) || (anfang % drei == 0) && (anfang !=3) || (anfang % fuenf == 0) && (anfang !=5) || (anfang % sieben == 0) && (anfang !=7))
 {
 cout << anfang << " ist keine Primzahl" << endl; 
 cout << endl;
 }
 else
 {
 cout << "Primzahl: " << anfang << "gefunden" << endl;
 cout << endl;
 }
 }

 return 0;
}

für mehr sicherheit in großen zahlenbereich , 11 und 13 nachm gleichen schema mit einführen.. dann denkste auch die 121 mit ab, mit 11

wäre die kack seite nicht off gewesen^^

chrisb · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Du hast den Algorithmus nicht ganz verstanden.

Da nach einigen Durchläufen der inneren for-Schleife die Abfrage "121 % 11 == 0" true wird, ist 121 keine Primzahl. Somit passt alles.

DasBoeseLebt · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Code:

// C++

#include <iostream>

using namespace std;

int main()
{
 
 int anfang = 0, ende = 0;
 const int zwei = 2;
 const int drei = 3;
 const int fuenf = 5;
 const int sieben = 7; 
 const int elf = 11;
 const int dreizehn = 13;


 do {
 cout <<"Bitte einen Anfangswert eingeben: ";
 cin >> anfang;

 cout << endl;

 cout << "Bitte einen Endwert eingeben: ";
 cin >> ende;

 cout << endl;

 } while(anfang < 0 || ende < anfang);


 for (anfang; anfang<ende; anfang++)
 {
 if ((anfang % zwei == 0) && (anfang != 2) || (anfang % drei == 0) && (anfang !=3) || (anfang % fuenf == 0) && (anfang !=5) || (anfang % sieben == 0) && (anfang !=7) 
 || (anfang % elf == 0) && (anfang !=11 ) || (anfang % dreizehn == 0) && (anfang !=13))
 {
 cout << anfang << " ist keine Primzahl" << endl; 
 cout << endl;
 }
 else
 {
 cout << "Primzahl: " << anfang << "gefunden" << endl;
 cout << endl;
 }
 }

 return 0;
}

Hier , bitte. mit 11 und 13 mitdrinnen, aber denke dran, in hohen zahlenbereich brauchste noch mehr . dann musst du kleinere primzahlen hinzufügen!

Ansonsten bug gefixt, dass Ende nicht kleiner als der anfang sein kann

edit: jaja, nicht gerade elegant, tut aber seinen zweck !!!

razor90 · 10. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Code:

#include <iostream>

using namespace std;

static const unsigned _START = 2;
static const unsigned _N = 1000;

int main()
{
 bool *isPrime = new bool[_N+1];

 for (unsigned i = 0; i <= _N; ++i)
 isPrime[i] = true;


 for (unsigned i = 2; i * i <= _N; ++i)
 {
 if (isPrime[i])
 {
 for (unsigned j = i*i; j <= _N; j += i)
 {
 isPrime[j] = false;
 }
 }
 }

 for (unsigned i = _START; i <= _N; ++i)
 if (isPrime[i])
 cout << i << " ist prim." << endl;

 return cin.get();
}

Mal ein anderer Ansatz: Alle Primzahlen von 2 bis _N berechnen und dann von _START an ausgeben

4poPh!5 · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

ehm, ich denke mal man kann das ganz einfach so machen:

Code:

#include <iostream>

using namespace std;

bool istPrim(int kandidat);

int main()
{
 for(int counter=2;counter<130;counter++)
 {
 bool primzahl=istPrim(counter);
 if (primzahl==true) 
 cout<<counter<<endl;
 else ;
 }
}

bool istPrim(int kandidat)
{
 for(int i=2;i<((kandidat/2)+1);i++)
 {
 if(kandidat%i==0)
 {
 return false;
 }
 }
 return true;
}

das Ganze schick in eine kleine Funktion ausgelagert, und nur wenns true zurück gibt, wird Primzahl ausgegeben.
Hab ich vor Ewigkeiten mal gemacht, und nur rausgesucht ^^.

greetz

Farin · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Die Lösung von 4poPh!5 ist richtig... Die sollte alle Primzahlen von anfangswert bis entwert ausgeben.

Desweiteren möchte ich noch erwähnen das 1 eine Primzahl ist... Irgendwo oben stand das das nicht der fall ist... Ist es aber... Denn sie ist nur duch sich selbst und durch 1 teilbar...

LG Farin

chrisb · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Das stimmt schon. Im Grunde macht dieser Algorithmus jedoch nichts anderes wie bloodyphoenix' bzw. meiner. Anstatt eine zweifach geschachtelte for-Schleife zu benutzen, lagert er die zentrale Prüfung in einer Funktion. Das ist schöner, darf der Threadersteller wahrscheinlich aber nicht für seine Lösung benutzen.

Rushh0ur · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Der Code von bloodyphoenix ist doch super ein wenig angepasst und man braucht auch keine Hilfsvariablen oder Funktionen (auser der Wurzel funktion, kann man aber auch die hälfte nehmen wie es zb. 4poPh!5 gemacht hat):

PHP:

    #include <math.h>

 
  [...]

 
for( i = anfang ;  i <= ende ;  i ++)

{    

    if (( i == 2 ) || ( i == 3 ))  cout  <<  "Bei " <<  i  << " ist eine Primzahl\n" ;

    else

    {

        for( j = 2 ;  j  <  sqrtl ( i );  j ++)

        { 

            if (  i % j  ==  0 )       break;

            if (  j + 1  >  sqrtl ( i ))  cout  <<  "Bei " <<  i  << " ist eine Primzahl\n" ;

        }

    }

}

@Farin

1 ist eine Primzahl, je nachdem wie man Primzahl definiert

Mfg Rushh0ur

Mr_MeYa · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Genau das.

Wie ich sehe fällt nicht nur mir das nicht einfach, gerade unter diesen Einschränkungen. Aber der Ansatz von DasBoeseLebt sieht echt gut aus

Ich bin am grübeln, wie ich den modulo immer um eins erhöhen kann, das dann als bedingung in eine If schleife, so das er den modulo auf einen zahlenbereich von z.B. 2 - 200 prüft, anstatt nur von 2 - 9.

DasBoeseLebt · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Du wirst leider nur das Problem bekommen, dass du ohne Algorithmus nicht nur primzahlen bekommen wirst, so sind gerade in hohen bereich auch nicht primzahlen drin. Zu Hause denk ich nochmal drüber nach.

Mr_MeYa · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Eine "Sicherheit" würde bis 1000 reichen.

Farin · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Da hast du vollkommen recht... aber man muss nur noch die beiden Funktionen kombinieren... und das sollte kein Problem sein... das sieht dann so aus ...

Ich habe es noch ein wenig modifiziert, damit auch 1 und 2 berücksichtigt werden...

PHP:

    #include <iostream>
  using  namespace  std ;
 
  int main (){
 
  int start  =  1 ;
  int stop  =  100000 ;
 
    for( int counter = start ; counter < stop ; counter ++)
    {
         bool primzahl  =  true ;
             //Damit 1 und 2 auch als Primzahl ausgegeben werden
             if(( counter  !=  1 ) && ( counter  !=  2 )){
                for( int i = 2 ; i <(( counter / 2 )+ 1 ); i ++){
                    if( counter % i == 0 ){
                     //Damit die schleife abgebrochen wird, falls die zahl Teilbar ist.
                     i  =  counter  /  2  +  1 ;
                         primzahl  =  false ;
                    }
                }
            }
 
        if ( primzahl == true ){
             cout << counter << endl ;
        }
    }
     system ( "Pause" );
}

@Rushh0ur sagte ich ja^^

@Threadersteller

Die Lösung von mir funktioniert -.-, sie nutzt nur schleifen ich hoffe das ist das was du haben wolltest

LG Farin

Mr_MeYa · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Ja, ich weiß das das funktioniert, aber du hast ne Flag benutzt. Das ist nicht erlaubt nach aufgabenstellung, so wärs ja einfach gewesen.

chrisb · 11. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Nun gut, Rushh0ur hat doch bereits eine Lösung ohne Flag gepostet. Was spricht gegen diese?

Also:

Code:

for (int p = start; p <= end; ++p) {
 for (int i = 2; i <= static_cast<int>(std::sqrt(p) + 1); ++i) {
 if (p % i == 0)
 break;
 if (i + 1 > static_cast<int>(std::sqrt(p) + 1))
 std::cout << p << " ist Primzahl." << std::endl;
 }
}

Bemerkung: Man kann mit Sicherheit sagen, dass p eine Primzahl ist, wenn nach dem i'ten Durchlauf die Schleife noch immer nicht durch break beendet wurde.

Mr_MeYa · 16. September 2009

AW: Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Ohne Typwandlungsorperator gehts nicht?

Habe ich mir schon fast gedacht...

Nützliche Suchen

[C/C++] Primzahlen zwischen Start- und Endwert ausgeben [nur mit for-Schleife]

Videos zum Themenbereich