Primärzahl

hallo ich bins wieder

ich habe ein programm geschrieben, welches eine zahl überprüft ob es sich um eine primärzahlen handelt.
jetzt möchte ich eure meinung dazu wissen. weil ich habe es nur geschat, dass er mir die zahlen angibt, welches sich durch die gewählte zahl teilen lassen.

# include <iostream.h>
void main ()
{   int n,k;
cin >> n;
for ( k=2;k<=n;k++)
{if (n%k==0)
cout << k<<endl;
}
}

knivil

Meinungen gibt es wie Sand am Meer. Stelle eine konkrete Frage!

SG1

Was ist bitte eine Primärzahl?

knivil

Ich hab 's auch googlen muessen. Eine Primzahl ... a) Fuer eine Primzahl muss der bei Division durch kleinere Zahlen (ausser 1) der Rest ungleich 0 sein. b) Oder anders: Es handelt sich um keine Primzahl, wenn bei Division durch eine kleinere ein Rest von 0 ueberig bleibt.

Also, die genau Frage lautet: Ist n eine Primzahl?

Dabei handelt es sich um eine Funktion, also schreiben wir die Signatur. Da es sich um eine Ja/Nein-Frage (wahr/falsch) handelt, ist der Rueckgabewert bool.

bool prim(int n)
{
  if (n == 1) return false; // Sonderfall fuer eins
  for(int i = 2; i < n; ++i)  // <-- nur Zahlen kleiner als n testen, weil n%n == 0 immer gilt
  {
    if (n%i == 0) return false; // <-- Variante b
  }

  return true;
}

ok du hast recht

dann will ich es mal so ausdrücken. ich möchte das mir das programm angibt ob sich die zahl um eine primzahl handelt oder nicht.
ich habe da eine idee aber kann es nicht in c++ umsetzen. und zwar soll der die zahlen ,welche sich durch die zuvor eingegebene zahl teilen lassen, zählen. sollten es mehr als eine zahl sein, die sich teilen lassen, dann ist es keine primzahl sonst ist es eine. es wird nur eine zahl benötigt, weil ich die 1 schon entfernt habe.

ich hoffe ich konnte mich korrekt ausdrücken

Was ist bitte eine Primärzahl?

oh das tut mir leid. hab wohl zu schnell geschrieben.
meine natürlich primzahl.

Bashar

Mohamedyarub schrieb:

ich habe da eine idee aber kann es nicht in c++ umsetzen. und zwar soll der die zahlen ,welche sich durch die zuvor eingegebene zahl teilen lassen, zählen. sollten es mehr als eine zahl sein, die sich teilen lassen, dann ist es keine primzahl sonst ist es eine. es wird nur eine zahl benötigt, weil ich die 1 schon entfernt habe.

Dein Programm mit dieser Idee (und mit weniger Fehlern):

#include <iostream>
using namespace std;
int main()
{
  int n;
  cin >> n;

  int teiler = 0;
  for (int k = 2; k <= n; k++)
  {
    if (n%k == 0)
       teiler++;
  }

  if (teiler > 1)
    cout << "Keine Primzahl!";
  else
    cout << "Primzahl!";
}

Verbesserung Nummer 1: Warum bis n zählen? n ist auf jeden Fall durch n teilbar.

#include <iostream>
using namespace std;
int main()
{
  int n;
  cin >> n;

  int teiler = 0;
  for (int k = 2; k < n; k++)
  {
    if (n%k == 0)
       teiler++;
  }

  if (teiler > 0)
    cout << "Keine Primzahl!";
  else
    cout << "Primzahl!";
}

Verbesserung 2: Warum muss ich nach einem Teiler noch weiterzählen? Ich könnte doch direkt aufhören.

#include <iostream>
using namespace std;
int main()
{
  int n;
  cin >> n;

  int teiler = 0;
  for (int k = 2; k < n; k++)
  {
    if (n%k == 0) {
       teiler++;
       break;
    }
  }

  if (teiler > 0)
    cout << "Keine Primzahl!";
  else
    cout << "Primzahl!";
}

Verbesserung drei: teiler kann jetzt nur 0 oder 1 sein, und mich interessiert auch nur ob 0 oder 1. Für solche ja/nein-Entscheidungen benutzt man boolesche Variablen:

#include <iostream>
using namespace std;
int main()
{
  int n;
  cin >> n;

  bool hatTeiler = false;
  for (int k = 2; k < n; k++)
  {
    if (n%k == 0) {
       hatTeiler = true;
       break;
    }
  }

  if (hatTeiler)
    cout << "Keine Primzahl!";
  else
    cout << "Primzahl!";
}

ja das sieht doch gut aus.
vielen dank
eine frage hätte ich da noch was genau bedeutet das? using namespace std;
das kenn ich noch nicht. ist das so wichtig?

Bashar

Mohamedyarub schrieb:

eine frage hätte ich da noch was genau bedeutet das? using namespace std;
das kenn ich noch nicht. ist das so wichtig?

http://fara.cs.uni-potsdam.de/~kaufmann/?page=GenCppFaqs&faq=iostream#Answ

knivil

Naja, eigentlich musst du z.B. std::cin schreiben. Du benutzt cin aus dem Namensraum std . Mit using gibst du den Namensraum direkt an und kannst das std:: vor cin weglassen. Bei dir klappt es auch ohne, da du iostream.h einbindest, wobei das sehr veraltet ist. Wenn du das aus einem Buch oder so hast, kaufe dir ein neues!

ich hab das jetzt so gemacht

#include <iostream.h>
void main()
{
  int n;
  cin >> n;

  int teiler = 0;
  for (int k = 2; k <= n; k++)
  {
    if (n%k == 0)
       teiler++;
  }

  if (teiler > 1)
    cout << "Keine Primzahl!";
  else
    cout << "Primzahl!";
}

und wegen iostream.h
ich habe das nicht aus dem buch sondern lerne das auf der uni. studiere Physik und haben als nebenfach noch informatik.
kenne das programmieren erst seit 2 monaten.

nochmal vielen dank an alle für eure schnellen und sehr guten antworten

knivil

Als Rat: Kaufe dir ein gutes Buch und vergiss den Unikurs.

kannst es auch mit dem beispiel versuchen, wo man die primzahlen bis hundert ausgibt ...

for( nCount = 1; nCount < 100; nCount += 2 )
{
	bIsPrim = 1;
	for( nDiv = 2; nDiv <= nCount / 2; nDiv+=2 )
	{
		if( nDiv == 4 )
			nDiv--;
		if( nCount % nDiv == 0 )
		{
			bIsPrim = 0;
			break;
		}
	}
	if( bIsPrim == 1 )
		printf( "%2d ist eine Primzahl\n", nCount );

soo long zai

zaiborg schrieb:

for( nDiv = 2; nDiv <= nCount / 2; nDiv+=2 )

Y U NO STOP AT SQRT(nCount) ???

C++ Forumbot

Dieser Thread wurde von Moderator/in Martin Richter aus dem Forum MFC (Visual C++) in das Forum C++ (auch C++0x und C++11) verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

unskilled

//edit: 1 vergessen... ^^

bool isprim(unsigned val)
{
  assert(val != 0);

  if(val == 1)
    return false;
  if(val < 4)
    return true;
  if(val%2 == 0)
    return false;

  for(unsigned i = 3; i < val; i += 2)
  {
    if(val%i == 0)
      return false;
    if(val/i < 2)
      break;
  }

  return true;
}

#include <iostream>

int main()
{
  for(unsigned in; std::cin >> in;)
  {
    if(isprim(in))
      std::cout << "Primzahl\n";
    else
      std::cout << "keine Primzahl\n";
  }
}

bb

314159265358979

#include <iostream>
#include <vector>

bool is_prime(unsigned n)
{
        if(n < 2)
                return false;

        if(n == 2 || n == 3)
                return true;

        if(n % 2 == 0 || n % 3 == 0)
                return false;

        for(unsigned i = 5, delta = 2; i * i <= n; i += delta, delta = 6 - delta)
                if(n % i == 0)
                        return false;

        return true;
}

template <typename T, typename A>
std::ostream& operator << (std::ostream& os, std::vector<T, A> const& v)
{
        os << '[';

        if(v.empty())
                return os << ']';

        os << v.front();

        for(auto iter = ++v.begin(); iter != v.end(); ++iter)
                os << ',' << *iter;

        return os << ']';
}

int main()
{
        unsigned const bounds[] = { 0, 150 };
        std::vector<int> primes;

        for(unsigned i = bounds[0]; i <= bounds[1]; ++i)
                if(is_prime(i))
                        primes.push_back(i);

        std::cout << primes;
}

Im Prinzip ähnlich der Version von unskilled, außer dass nicht nur Vielfache von 2, sondern direkt Vielfache von 2 und 3 überprungen werden. (Auf i wird abwechselt 2 und 4 addiert.)

http://ideone.com/Mmje2

Und weil ich gerade Langeweile hab, hier nochmal das ganze in Haskell.

isPrimeImpl n i delta
        | i * i > n      = True
        | n `mod` i == 0 = False
        | otherwise      = isPrimeImpl n (i + delta) (6 - delta)

isPrime n
        | n < 2                            = False
        | n `elem` [2, 3]                  = True
        | n `mod` 2 == 0 || n `mod` 3 == 0 = False
        | otherwise                        = isPrimeImpl n 5 2

main = print $ filter isPrime [1 .. 150]

http://ideone.com/Bs60a

Nicht weil du Langeweile hast. Weil du allen zeigen willst, wie toll du in Haskell h4xX0rn kannst

314159265358979

Haskell ist halt sexy.

unskilled

...und bis auf die tatsache, dass bei mir 1 ne primzahl ist, weil ich nen trottel bin