Wie generieren Sie einen Benutzer definierte Menge von Primzahlen?

Question

Ich versuche, Primzahlen zu erzeugen, basierend auf Benutzereingaben. Das ist, was ich habe, so weit, aber ich kann einfach nicht scheinen, um es herauszufinden:

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for

Answer 1

Es soll möglich sein, zu sehen, warum Ihre Ergebnisse falsch sind ganz einfach, wenn Sie an Ihrem Schleifenstruktur aussehen. Schritt für Schritt durch sie mit der Hand (es wird nicht lange dauern).

Der Grund, dass Sie Ihre aktuellen Ergebnisse bekommen ist, dass nicht jede Iteration der äußeren Schleife (x < numberOfPrimes) ein Ergebnis erzeugt - es ziemlich viele Iterationen überspringen wird aufgrund der Art und Weise der inneren Schleife strukturiert ist,

.

Was Sie wirklich brauchen, zu tun ist, Umstrukturierung der inneren Schleifen. Ihre innerste Schleife funktioniert gut, und sollten alle Primzahlen erkennen. Ihre zweite Schleife sollte jedoch nur Zahlen testen, die noch nicht getestet. Außerdem sollten sie aufhören looping, sobald Sie eine Primzahl finden.

Answer 2

Sie sollten Ihren Code besser strukturieren, es ist wirklich die Art und Weise unordentlich Sie es jetzt tun. Haben Sie eine Methode IsPrime(int x) die true zurück, wenn x prim ist und andernfalls false.

Dann numberOfPrimes Primzahlen zu erzeugen, können Sie etwas tun:

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

oder verwenden Sie das Sieb des Eratosthenes , die eine viel schnellere Methode ist.

Um herauszufinden, ob eine Zahl x Primzahl ist oder nicht, versuchen alle seine Faktoren zwischen 2 und Sqrt(x). Warum nur Sqrt(x)? Denn wenn a*b = x, dann x / b = a und x / a = b, also würden Sie alles zweimal überprüfen, und auch Dinge überprüfen Sie nicht sollen, wenn Sie geht bis x / 2 oder sogar x.

So etwas wie dies, wenn Sie die IsPrime(x) Funktion verwenden möchten:

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

Aber ich schlage vor, Sie das Sieb des Eratosthenes verwenden, da es viel schneller ist. Sie können auch Dinge optimieren, so dass Sie nicht einmal Zahlen überprüfen, da eine gerade Zahl ist nie eine Primzahl ist, mit Ausnahme von 2 (beide im Sieb und die naiven Methode). Behandle x = 2 als Kantenfall und dann beginnt jede andere Zahl Überprüfen (3, 5, 7, 9, 11 etc.)

Answer 3

Was Sie suchen wird als „Sieb des Eratosthenes.“ Da ich nicht die Leute in den Hausaufgaben zu machen bin, dann ist dies der einzige Anhaltspunkt ich dir geben werde. Der Algorithmus ist leicht im Internet zu finden.

Answer 4

Die nächste Primzahl (x) - ist die Zahl, die durch alle Primzahlen s unterteilt werden kann nicht, dass s <= sqrt (x). So können Sie Funktion wie verwenden

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

Und als man Primzahlen wie

bekommen

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);

Answer 5

var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

von codethinked.com

kopiert

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

    for (int i = 3; i < m; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}

Answer 6

1. Benennen Sie Ihre Variablen.

Erstens, wenn diese Hausaufgaben werden Sie schlechte Noten erhalten (wenn Ihr Lehrer sein Geld wert ist), weil Sie bedeutungslos Variablennamen (ja, auch numberOfPrimes falsch ist und requiredNumberOfPrimes benannt werden sollte. Wenn ich diese Variable sehen Ich frage mir ‚ist dies, wie viele er will, oder wie viele er gefunden hat?‘).

Zweitens, es wird Ihnen helfen zu verstehen, wo Sie falsch gehen. Variablen sollten logisch benannt werden nach dem, was sie darstellen. Wenn Sie nicht erklären können, was Ihre Variablen darstellen (zum Beispiel a & b), dann kann man wohl nicht erklären, was Sie mit ihnen tun.

2. Schauen Sie sich Ihre Loops.

for (int x = 0; x < numberOfPrimes; x++)

Die Struktur einer for-Schleife ist (initialise; 'should I continue?'; 'each loop do this'). Daher in der Schleife

• Sie sind bis x weiterhin gleich oder großer als numberOfPrimes *.
• Jedes Mal, wenn die Schleife durchlaufen Sie 1 bis x hinzufügen.

Sind Sie sicher, dass das, was Sie tun wollen? x erscheint die Anzahl der Primzahlen darstellen Sie gefunden haben. Also, warum es nicht erhöht werden, wenn Sie einen erstklassigen finden, anstatt, wenn Sie eine Schleife starten?

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

Sie befinden sich bei jeder ganzen Zahl zwischen 2 und x, inklusive. Und für jedes dieser ganzen Zahlen a, suchen Sie bei jeder ganzen Zahl zwischen a bis einschließlich 2. Was werden Sie mit diesen Zahlen zu tun?

Jedes Mal, wenn Sie eine Schleife durch Ihre Top-Level-Schleife (die x Loop), werden Sie Ihre a Schleife von Grund auf neu zu starten, und jedes Mal, wenn Sie eine Schleife durch Ihre a Schleife werden Sie Ihre b Schleife von vorne anfangen.

Also, wenn x 10, Sie laufen durch eine einmal (a = 2), dann führen Sie durch eine wieder (a = 2, a = 3), dann führen Sie durch eine wieder (a = 2, a = 3 , a = 4), dann ...

3. Sammeln Sie Ihre Ergebnisse, anstatt sie zu Console zu schreiben.

var primes = new List<int>();

Es ist so einfach. Wenn Sie eine erstklassige, primes.Add(a); finden. Dann wissen Sie, wie viele Primzahlen Sie gefunden haben (primes.Count), können Sie die Liste der Primzahlen verwenden, um effizient die nächste Primzahl zu bestimmen, und Sie können die Liste verwenden, später, falls erforderlich.

Answer 7

Wenn Sie ithe tun bekommen Schleifen aussortiert, Sie müssen nur für b überprüfen