Rozkład liczby na czynniki pierwsze

Każdą liczbę naturalną za wyjątkiem liczb pierwszych można rozłożyć na czynniki pierwsze, które po przemnożeniu dają wartość liczby rozkładanej.

Przykładowo liczba 18 rozkłada się na takie czynniki

2 ⋅ 3 ⋅ 3 = 18

Liczba 92 rozkłada się na takie czynniki

2 ⋅ 2 ⋅ 23

Jak widać kolejne czynniki w/w rozkładach to liczby pierwsze.

Algorytm rozkładu dowolnej liczby naturalnej polega na szukaniu kolejnych dzielników, będącymi liczbami pierwszymi. Powtarzany krok wyznaczania takich dzielników kończy się w momencie uzyskania wartości 1. Rachunek wykonywanie w algorytmie można przedstawić jak poniżej (pionowa kreska oznacza dzielenie)

Rozkład liczby

Schemat algorytmu rozkładu liczby na czynniki pierwsze

Schemat algorytmu rozkładu liczby na czynniki pierwsze

Uwaga: Algorytm jest zapisany pod aplikację deskotopową w C# dla Visual Studio, stąd instrukcja tb.AppendText(i.ToString()). Dla niezorientowanych w C# instrukcja ta oznacza dopisanie kolejnego wiersza w kontrolce klasy TextBox. W rozwiązaniu dla konsoli, na przykład w C++, należałoby zastosować instrukcję wysłania zmiennej na ekran (cout << i)

Kod funkcji realizującej algorytmu rozkładu liczby na czynniki pierwsze

Wskazówka:


private void rozlozNaCzynnikiPierwsze(int n, TextBox tb)
        {
            int i = 2;//ustaw na pierwszą liczbę pierwszą
            while(n>1)
            {
                while (n % i == 0)//sprawdź czy i-ta jest dzielnikiem
                {
                    //dopisz kolejny wierzs z wynikiem
                    tb.AppendText(i.ToString() + Environment.NewLine);
                    n = n/i;
                }
                i++;
            }
        }

Przykładowa aplikacja wyznaczająca rozkład liczby na czynniki pierwsze

aplikacja wyznaczająca rozkład liczby na czynniki pierwsze

Pełny kod klasy Form utworzonej formatki aplikacji

Form1.cs


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace _4AlgRozkladLiczbyNaCzynnikiPierwsze
{
    public partial class Form1 : Form
    {
        private void rozlozNaCzynnikiPierwsze(int n, TextBox tb)
        {
            int i = 2;//ustaw na pierwszą liczbę pierwszą
            while(n>1)
            {
                while (n % i == 0)//sprawdź czy i-ta jest dzielnikiem
                {
                    //dopisz kolejny wierzs z wynikiem
                    tb.AppendText(i.ToString() + Environment.NewLine);
                    n = n/i;
                }
                i++;
            }
        }
        public Form1()
        {
            InitializeComponent();
        }

        private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
        {
            if(e.KeyChar == 8) return;//wyskocz na BackSpace
            if(e.KeyChar<'0'||e.KeyChar>'9')e.Handled = true;//ignoruj nienumeryczne
        }

        private void button1_Click(object sender, EventArgs e)
        {
            if (textBox1.Text.Length < 1) return;
            int n= Convert.ToInt32(textBox1.Text);
            textBox2.Clear();
            rozlozNaCzynnikiPierwsze(n, textBox2);
        }
    }
}
Alkomat- wirtualny test

Alkomat- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play