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 = 18Liczba 92 rozkłada się na takie czynniki
2 ⋅ 2 ⋅ 23Jak 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);
}
}
}
