aFizyka logo

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ą

Algorytm badania pierwszości liczb. Visual studio C#

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

aplikacja badania pierwszości liczb. Visual studio C#

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