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)

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

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);
        }
    }
}

Rozwiązanie pod konsolę

Poniżej zrzut ekranu rozwiązania konsolowego

aplikacja wyznaczająca rozkład liczby na czynniki pierwsze konsola

Kod aplikacji konsolowej przedstawia się jak poniżej

Form1.cs


namespace rozklad_liczby_na_czynniki_pierwsze
{
    internal class Program
    {
        static void rozlozNaCzynnikiPierwsze(int n)
        {
            Console.WriteLine("Czynniki pierwsze dla liczby "+ n +" to:");
            int i = 2;//ustaw na pierwszą liczbę pierwszą
            while (n > 1)
            {
                while (n % i == 0)//sprawdź czy i-ta jest dzielnikiem
                {
                    //dopisz kolejny wiersz z wynikiem
                    Console.WriteLine(i);
                    n = n / i;
                }
                i++;
            }
        }
        static void Main(string[] args)
        {
            Console.WriteLine("Witaj w CzD!");
            Console.WriteLine("Podaj liczbę całkowitą: ");
            int n = int.Parse(Console.ReadLine());
            rozlozNaCzynnikiPierwsze(n);
        }
    }
}