Algorytm badania pierwszości liczb
Liczba pierwsza to liczba naturalna większa od 1, która ma tylko dwa dzielniki naturalne: jedynkę i samą siebie. Przykład kilku liczb pierwszych to: 2, 3, 5, 7, 11, 13
Aby sprawdzić czy podana liczba jest pierwsza, to należy wyszukać wszystkie jej dzielniki większe od 1 i mniejsze od niej samej. Jeżeli się takich nie znajdzie, to znaczy, że badana liczba jest liczbą pierwszą.
Realizacja takiego algorytmu będzie polegać na wykonaniu pętli szukania reszty z dzielenia dla kolejnych kandydatów na dzielniki. Znalezienie dzielnika (czyli reszta z dzielenia wynosi 0) oznacza, że dana liczba nie jest liczbą pierwszą.
Zakres przeszukiwania można zmniejszyć (co przyspiesza działanie algorytmu), jeżeli górną granicę określimy na wartość pierwiastka kwadratowego z badanej liczby. Wynik pierwiastkowania zaokrąglamy w dół.
Schemat algorytmu sprawdzającego czy podana liczba jest liczbą pierwszą
Ciało funkcji realizującej powyższy algorytm (język C#)
Wskazówka:
private bool czy_jest_pierwsza(int n)
{
int m = (int)Math.Floor(Math.Sqrt(n));
for (int i = 2; i <= m; i++)
if (n % i == 0) return false;//nie jest pierwszą
//jest pierwszą
return true;
}
Przykładowa aplikacja badająca pierwszość liczb napisana w Visual Studio
Pełny kod pliku 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 _2AlgCzyLiczbaJestPierwsz
{
public partial class Form1 : Form
{
private bool czy_jest_pierwsza(int n)
{
int m = (int)Math.Floor(Math.Sqrt(n));
for (int i = 2; i <= m; i++)
if (n % i == 0) return false;//nie jest pierwszą
//jest pierwszą
return true;
}
public Form1()
{
InitializeComponent();
}
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
//zabezpiecz przed znakami nienumerycznymi
if (e.KeyChar == 8) return;//wyskocz jak BackSpace
if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled = true;
}
private void button1_Click(object sender, EventArgs e)
{
if (textBox1.Text.Length < 1) return;
int liczba=Int32.Parse(textBox1.Text);
if (czy_jest_pierwsza(liczba))
MessageBox.Show("To jest liczba pierwsza",
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
else
MessageBox.Show("To nie jest liczba pierwsza",
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
}
private void button2_Click(object sender, EventArgs e)
{
//wyskocz bo nie podano górnego zakresu
if (textBox2.Text.Length < 1) return;
textBox3.Clear();
int i= 2,k= Int32.Parse(textBox2.Text);
while (i < k)
{
if (czy_jest_pierwsza(i))
textBox3.AppendText(i.ToString()+Environment.NewLine);
i++;
}
}
}
}
