Ruby, Primfaktoren zu gegebener Zahl errechnen?

Guten Tag, ich programmiere derzeit ein wenig mit Ruby und versuche nun, die in der Fragestellung erwähnte Aktion durchzuführen.

Ich weiß, wie ich Primzahlen errechne, aber ich weiß nicht, wie ich weiterarbeiten soll.

Die Antworten zu dieser Frage: https://www.gutefrage.net/frage/primfaktorzerlegung-mathe halfen mir ein wenig weiter, aber nicht sehr viel.

Kann mir jemand schnell aushelfen? Zumindest die richtige Richtung weisen?

Liebe Grüße

2 Antworten

PeterKremsner

20.11.2017, 22:45

Ich kann zwar kein Ruby kann dir aber den Algorithmus etwas erklären, die Implementierung in der Sprache musst du dann übernehmen.

Wenn man eine Liste von allen Primzahlen kennt welche kleiner als die Eingabe sind dann kann man so vorgehen, beginnend mit dem kleinsten Primfaktor 2.

Teile die Zahl solange durch den Primfaktor bis die Division einen Rest liefert (Modulo Primfaktor == 0, wenn ja dann ist es teilbar, else Punkt2)
Gehe zur nächsten Primzahl in der Liste
Wenn die nächste Primzahl höher ist als die Eingabe hast du alle Primfaktoren gefunden

Der Algorithmus basiert auf der annahme, dass man die Primzahlen kennt, wenn das nicht der Fall ist muss man diese Berechnen.

Jetzt kann man vorher mit einem Algorithmus die primzahlen von 2 bis zur Eingegebene Zahl durchlaufen und sich so die Liste on the fly bilden, oder man strukturiert etwas um.

In dem oberen Algorithmus kann man auch fragen ist die Zahl durch 2 3 oder ungerade Zahlen teilbar, was in diesem Fall auf das selbe Ergebnis kommt.

Also kann man eine Schleife machen und zunächst Prüfen wie oft ist die Zahl ganz durch zwei Teilbar. (Dann hast du die Menge der 2er bei der Primfaktorzerlegung)

Wie oft ist die Zahl welche nicht mehr durch 2 Teilbar ist durch 3 Teilbar (Menge der 3er in der Zerlegung)

Wie oft ist die Zahl welche jetzt nicht mehr durch 2 und 3 teilbar ist durch 3+n*2 teilbar n ist dabei eine Zahl von 1 bis unendlich.

Wenn 3+n*2 größer der eingebenen Zahl ist bist du fertig.

20202020202020

Fragesteller

20.11.2017, 23:55

Vielen Dank, aber ich schaffe es trotzdem einfach nicht...

PeterKremsner

21.11.2017, 10:20

@20202020202020

Würde dir C# oder C Code helfen?

RIDDICC

20.11.2017, 22:37

das ist doch das Sieb des Eratosthenes... oda?

sei die gegebene Zahl X.
dann testet man sie auf Teilbarkeit (ohne Rest) durch 2, 3, 5, 7, ..., P (also alle Primzahlen, die kleiner als Wurzel(X) sind)...
wenn man einen Teiler T findet, hat man auch gleichzeitig einen zweiten Teiler gefunden (nämlich X/T)...
dann macht man also weiter bis P, um alle Primfaktoren zu finden...

20202020202020

Fragesteller

20.11.2017, 23:55

Danke für die Hilfe, ich schaffe es aber trotzdem nicht, ich kriege nicht einmal einen Anfang hin...

RIDDICC

21.11.2017, 06:58

@20202020202020

ach je... :)

man bräuchte ne Funktion, die den kleinsten Primfaktor einer übergebenen Zahl A findet (wenn man bis Wurzel(A) nix findet, dann ist es automatisch ne Primzahl und man kann A zurückgeben)...
dazu sollte die eine Liste von Primzahlen erzeugen, damit die Funktion nicht Schnecken-langsam ist...
oder man gibt diese Liste fest vor...
oder man testet erst 2 (die kleinste Primzahl) und dann 2·n+1 für n=1,2,3,... (wenn man sich an die Reihenfolge für die Werte von n hält, dann müsste man automatisch auf ein n stoßen, dass eine Primzahl ist...)...

Ähnliche Fragen

Kommen otis und Ruby zusammen?

...zur Frage

Gehalt Rangierbegleiter bei der Deutschen Bahn?

Hallo Freunde ,

ich habe das Glück das ich wohl bald bei der deutschen Bahn als Rangierbegleiter arbeiten werde. Kann mir wer sagen wie hoch der Nettoverdienst ca ist wenn man mit 2360€ Brutto ( ohne Zuschläge ) anfängt ?

Ich weiß das ich viel Nachts arbeiten werde und das eine oder andere mal auch auf Montage gehen muss.

Kann mir wer nen Rechenweg zeigen wie ich meinen Stundenlohn errechne um dann mit den Nachtzulagen etc meinen Lohn zu errechnen? Ich habe einfach Angst das ich evtl zu wenig verdienen werde.

...zur Frage

Oshi no ko Kapitel 123 Aqua X Ruby?

Hallo ich wollte mal fragen was ihr denkt was pasiren wird Denkt ihr Es wird ein Aqau X Ruby gebeb oder was noch pasiren könte

...zur Frage

Ruby ausführen (Windows)?

Hi zusammen,

heute hatte ich meinen 1.Kontakt mit Ruby.
Leider blicke ich nicht überhaupt durch.

Mir wurde ein Programm zu Testzwecken zugeschickt. Das Programm sollte funktionieren. Leider weiß ich noch nicht wie man die Dateien mit Windows zum laufen bringt.

Ich habe Ruby installiert und kann die Software über CMDER starten. Nun frage ich mich wie man das ganze Anwenderfreundlich mit einem Explorer oder sonst wie starten/betrachten kann.

Habt ihr vielleicht Tipps für mich wie ich an die Sache ran gehen kann? .

...zur Frage

Wie oder wann kriegt man den Shadow Ruby Skin in FN?

Ich hab gehört das dass ein FN Next Gen Paket ist was gratis sein soll.

Habt ihr nähere Infos?

...zur Frage

Passen Aqua und Ruby perfekt zusammen?

Ich geb zu Akane mag ich am wenigsten und kana mehr aber ich finde beide passen nicht zu Aqua. Ich weiß Ruby und Aqua sind Geschwister aber sie Würden wiedergeboren also Könnte Aqua Ruby als Sina lieben und Ruby Aqua Als Sensei

...zur Frage

Lohnt es sich Ruby on Rails zu lernen?

...zur Frage

Welcher Name für den Hauptcharakter?

Was findet ihr besser? : Ruby Silverstone oder Luna Silverstone?

...zur Frage

Welche von den Programmiersprachen sollte ich als erstes lernen?

Java, Javascript, C#, PHP, C++, Python, C, SQL, Ruby, Objective-C

...zur Frage

Was ist eure lieblings Programmiersprache in 2023?

...zur Frage

Ruby Unterordner in einem Ordner auflisten?

Wie kann man in ruby die vorhandenen Unterordner in einem Ordner auflisten? Ich brauche nur die Ordnernamen?

...zur Frage

c# Primzahlen?

Hey liebe Community,

ich hätte da mal eine Frage. Ich habe die Möglichkeit, meinen Code etwas zu verändern. Bisher habe ich mit dem Code geprüft, ob die Eingabe des Benutzers eine Primzahl ist. Wie könnte ich es machen, dass z.B. der Benutzer eine Zahl eingibt (4) und die ersten vier Primzahlen ausgegeben werden?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Primzahlen
{
  class Program
  {
    static bool Primzahl(int primzahl)
    {
      bool ergebnis = false;
      int zähler = 0;

      for (int i = 1; i <= primzahl; ++i) // Zahl wird durch Teiler geteilt
      {
        if (primzahl % i == 0) //Teilung ohne Restwert, dann für 1 zum Zähler hinzufügen
        {
          zähler = ++zähler;
        }
      }

      if (zähler == 2) //Wenn Zahl nur durch sich und 1 teilbar ist, Ausgabe (Da Zähler auf 2 ist)
      {
        ergebnis = true;
      }

      return ergebnis;
    }

    static void Main(string[] args)
    {
      Console.Title = "Primzahlen";
      StreamWriter sw = new StreamWriter("Primzahlen.txt");

      Console.WriteLine("Geben Sie eine Zahl ein");
      string eingabe = Console.ReadLine();
      sw.WriteLine(eingabe);
      sw.Close();

      String dateiName = "Primzahlen.txt";
      StreamReader reader = null;
      int zahl = 0;
    
      try
      {
        reader = new StreamReader(dateiName);
        string zeile = reader.ReadLine();
        zahl = Convert.ToInt32(zeile);
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
      finally
      {
        if (reader != null)
          reader.Close();
      }

      if (Primzahl(zahl))
      {
        Console.WriteLine("Das ist eine Primzahl");
      }
      else
      {
        Console.WriteLine("Keine Primzahl");
      }

      Console.ReadLine();
    }
  }
}

Vielen Dank!

...zur Frage

Java: Wie funktioniert dieser Primzahlengenerator?

public static List<Integer> generateNumbers(int border) {
  List<Integer> finalList = new ArrayList<>();
  boolean[] bool = new boolean[border];

  for (int i = 0; i < bool.length; i++) {
    bool[i] = true;
  }

  /////////
  for (int i = 2; i < Math.sqrt(border); i++) {
    if (bool[i] == true) {
      for (int j = (i * i); j < border; j = j + i) {
        bool[j] = false;
      }
    }
  }
  ////////

  for (int i = 2; i < bool.length; i++) {
    if (bool[i] == true) {
      finalList.add(i);
    }
  }

  return finalList;
}

Mir geht es vor allem um den Bereich, welcher in den ///////// drinnen liegt, wo ich die Nicht-Primzahlen herausfische. Kann mir jemand diese for-Schleife Schritt für Schritt erklären?

...zur Frage

Ruby oder Rue als Vorname schöner?

Hi,

findet ihr Rue oder Ruby mit der Abkürzung Rue als Vorname besser?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen