C-keeles algarvu kontrollimine: algoritmid, näited ja tõhusad lahendused

1. Sissejuhatus

C-keel on laialdaselt kasutatav süsteemiarenduses ja manussüsteemides, kuna see võimaldab luua kiireid ja tõhusaid programme. Selles artiklis selgitame üksikasjalikult, kuidas C-keeles realiseerida “algoritm algarvude tuvastamiseks”.

Algarv on naturaalarv, millel ei ole positiivseid jagajaid peale 1 ja arvu enda. Näiteks 2, 3, 5 ja 7 on algarvud, kuid 4 ja 6 ei ole. Algarvudel on oluline roll krüptograafias ja matemaatiliste probleemide lahendamisel.

Selles artiklis käsitleme samm-sammult, kuidas C-keeles kirjutada lihtne programm algarvu tuvastamiseks ning seejärel ka tõhusamaid algoritme. Sisu sobib nii algajatele kui ka kesktasemel programmeerijatele, seega loe kindlasti lõpuni.

2. Mis on algarv?

Algarvu definitsioon

Algarv (Prime Number) on naturaalarv, mis on suurem kui 1 ja millel ei ole jagajaid peale 1 ja arvu enda.

Näiteid algarvudest

Allpool on mõned väiksemad algarvud:

• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Oluline on märkida, et 2 on ainus paarisarvuline algarv. Kõik teised algarvud on paaritud.

Miks algarvud on olulised

Algarvud on tähtsad mitte ainult matemaatikas, vaid ka infotehnoloogias ja krüptograafias. Eriti krüpteerimisalgoritmides kasutatakse laialdaselt suuri algarve turvasüsteemide loomiseks.

Algarvud ja C-keel

C-keel sobib hästi algarvude kontrollimiseks, kuna see võimaldab tõhusat täisarvude töötlemist ja suurte andmemahtude käitlemist. Järgmises jaotises tutvustame konkreetseid C-keele lahendusi algarvude tuvastamiseks.

3. Algarvude kontrollimine C-keeles

Põhiline algoritm

Lihtsaim viis kontrollida, kas arv on algarv, koosneb kahest sammust:

1. Kui arv (n) on väiksem kui 2, siis see ei ole algarv.
2. Jaga (n) kõigi täisarvudega vahemikus 2 kuni (sqrt{n}); kui jagamine annab jäägi 0, ei ole arv algarv.

Seda meetodit nimetatakse “jagamis­testiks” ja see sobib hästi väiksemate arvude kontrollimiseks.

Põhiline näidis C-keeles

Järgmine programm kontrollib, kas kasutaja sisestatud arv on algarv:

#include <stdio.h>
#include <math.h>

// Funktsioon algarvu kontrollimiseks
int is_prime(int n) {
    if (n <= 1) return 0;  // Väiksemad kui 2 ei ole algarvud
    if (n == 2) return 1;  // 2 on algarv
    if (n % 2 == 0) return 0;  // Paarisarvud (v.a 2) ei ole algarvud

    // Kontrollime ainult paarituid arve
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;  // Kui jagub, pole algarv
    }
    return 1;  // On algarv
}

int main() {
    int num;

    // Sisend
    printf("Sisesta täisarv: ");
    scanf("%d", &num);

    // Kontroll ja väljund
    if (is_prime(num))
        printf("%d on algarv.\n", num);
    else
        printf("%d ei ole algarv.\n", num);

    return 0;
}

Koodi selgitus

1. Päisefailide kaasamine

• <stdio.h>: standardne sisend/väljund teek.
• <math.h>: vajalik sqrt funktsiooni jaoks.

1. Funktsioon is_prime

• Kui n <= 1, pole tegemist algarvuga.
• 2 käsitletakse erandina algarvuna.
• Paarisarvud (peale 2) jäetakse kohe välja.
• Kontrollitakse ainult paarituid, vähendades arvutuste arvu poole võrra.

1. Kontroll kuni ruutjuureni

• Kuna jagajad esinevad sümmeetriliselt, piisab kontrollist kuni sqrt(n).

1. Kasutaja sisend ja väljund

• Kasutajalt küsitakse arvu, kontrollitakse ja kuvatakse tulemus ekraanile.

4. Tõhusamad algoritmid

Kiirendamise võtted

Lihtne algarvu kontroll sobib väikeste arvude jaoks, kuid suurte arvude korral suureneb arvutusaeg. Tõhusust saab parandada järgmiselt:

1. Paarisarvude välistamine

• Kontrollime ainult paarituid arve, välja arvatud arv 2.

1. Kontroll ainult kuni ruutjuureni

• Jagajaid on sümmeetriliselt, seega pole vaja kontrollida kaugemale kui sqrt(n).

1. Eelkontroll väikeste algarvudega

• Välistame kohe arvud, mis jaguvad näiteks 2, 3, 5 või 7-ga.

Eratosthenese sõel

Eratosthenese sõel on algoritm, mis leiab kõik algarvud etteantud vahemikus. Sammud:

1. Algseadistus

• Loome loendi ja märgime kõik arvud algarvukandidaadiks.

1. Kordsete eemaldamine

• Alustame arvust 2 ja märgime kõik tema kordsed mitte-algarvuks.

1. Lõpetamistingimus

• Kui kontrollitav arv ületab ruutjuure, lõpetame protsessi.

Eratosthenese sõela näidis C-keeles

#include <stdio.h>
#include <stdbool.h>

#define MAX 1000  // Vahemiku ülempiir

void sieve_of_eratosthenes(int n) {
    bool prime[n + 1];
    for (int i = 0; i <= n; i++)
        prime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    printf("Algarvude nimekiri:\n");
    for (int i = 2; i <= n; i++) {
        if (prime[i])
            printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int limit;
    printf("Sisesta vahemiku ülempiir: ");
    scanf("%d", &limit);

    if (limit < 2) {
        printf("Palun sisesta väärtus vähemalt 2.\n");
        return 1;
    }

    sieve_of_eratosthenes(limit);
    return 0;
}

Koodi selgitus

1. Massiivi prime[] algväärtustamine

• Märgime kõik alguses tõeks (algarvukandidaat).

1. Kordsete eemaldamine

• Alustame 2-st ja eemaldame kõik tema kordsed.

1. Kontroll alates p^2

• Vähendab tarbetuid arvutusi, sest väiksemad kordsed on juba eemaldatud.

1. Tulemuse väljastamine

• Kuvame ainult need arvud, mis jäid märgituks kui true.

5. Rakenduse tähelepanekud

1. Suurte arvude käsitlemine

Probleem
C-keeles sõltub täisarvu (int) suurus keskkonnast; 32-bitises süsteemis on maksimaalne väärtus umbes 2,147,483,647. Suuremate arvude jaoks on vaja täiendavaid meetmeid.

Lahendused

1. long long int kasutamine

• Võimaldab käsitleda kuni umbes 9 kvintiljoni (9,223,372,036,854,775,807).

long long int num = 9223372036854775807LL;

2. Väliste teekide kasutamine

• Näiteks GMP (GNU MP) teek mitme täpsusega täisarvude käsitlemiseks.

#include <gmp.h>
mpz_t num;
mpz_init(num);

2. Arvutusmahu ja jõudluse optimeerimine

Probleem
Algarvude kontroll võib olla arvutusmahukas, eriti suurte vahemike korral.

Optimeerimisviisid

1. Mälusäilituse (cache) kasutamine

• Salvesta juba kontrollitud tulemused, et vältida kordusarvutusi.

1. Paralleeltöötlus

• Kasuta mitmelõimelist töötlemist või OpenMP-d kiiruse tõstmiseks.

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    // Paralleeltöötlus
}

3. Õige algoritmi valik

• Väiksemate arvude puhul sobib jagamistest, suuremate puhul Eratosthenese sõel.

3. Vigade käitlemise olulisus

Miks see on oluline
Võimalikud vead:

• Vigane sisend: negatiivsed arvud, null või mitte-arvulised väärtused.
• Ületäitumine: liiga suur arv ületab andmetüübi piiri.

Lahendused

1. Sisendi valideerimine

• Lubatakse ainult kehtivad täisarvud.

int num;
printf("Sisesta täisarv: ");
if (scanf("%d", &num) != 1) {
    printf("Vigane sisend.\n");
    return 1;
}

2. Vahemiku piiramine

• Seadista mõistlikud piirid, et vältida ressursiprobleeme.

3. Mäluleke vältimine

• Kui kasutatakse dünaamilist mälu, vabastada see enne programmi lõppu.

4. Koodi loetavus ja hooldatavus

Probleem
Liiga keerukas kood vähendab hooldatavust ja arusaadavust.

Soovitused

1. Funktsioonide jaotamine

• Jagada kood funktsioonideks vastavalt funktsionaalsusele.

1. Kommentaaride lisamine

• Selgita iga olulise osa eesmärk ja tööpõhimõte.

1. Tähenduslikud muutujanimed

• Kasutada selgeid nimesid, nt input_number asemel num.

6. Näited programmi käivitamisest

Siin näitame, kuidas eelnevad C-keele programmid töötavad ja millist väljundit need annavad.

Lihtne algarvukontroll

整数を入力してください: 17
17 on algarv.

整数を入力してください: 18
18 ei ole algarv.

整数を入力してください: 1
1 ei ole algarv.

整数を入力してください: -5
-5 ei ole algarv.

Eratosthenese sõel

Sisesta vahemiku ülempiir: 50
Algarvude nimekiri:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Tähelepanekud käivitamisel

1. Sisendi piiramine

• Väga suur sisend võib põhjustada mälupuudust või jõudluse langust.

1. Vigade kontroll

• Veendu, et vigane sisend annab selge veateate.

1. Keskkonnast sõltuv käitumine

• Kontrolli programmi tööd eri kompilaatorite ja süsteemide all.

7. Kokkuvõte

Selles artiklis õppisime C-keeles algarvude kontrollimist alates lihtsatest algoritmidest kuni tõhusamate meetoditeni.

Olulised punktid

1. Mis on algarv

• Algarv on naturaalarv, millel on ainult kaks jagajat: 1 ja tema ise.

1. Põhiline kontroll C-keeles

• Lihtne jagamistest koos kontrolliga kuni ruutjuureni.

1. Tõhusad algoritmid

• Eratosthenese sõel sobib suuremate andmemahtude jaoks.

1. Rakendusnõuanded

• Suurte arvude käsitlemine, jõudluse optimeerimine ja vigade kontroll.

1. Näited ja väljund

• Praktilised näited aitavad kinnistada õpitud põhimõtteid.

Edasised sammud

1. Keerukamad algoritmid: nt Miller-Rabini või AKS-i test.
2. Krüptograafia rakendused: nt RSA-algoritmi loomine.
3. Paralleeltöötlus ja optimeerimine suurte andmemahtude jaoks.
4. Teistes keeltes realiseerimine: nt Python või C++.

Lõppsõna

Algarvude kontroll on programmeerimise alus, millel on rakendusi nii matemaatikas kui ka infotehnoloogias. C-keele valdamine selles vallas loob tugeva aluse edasisteks projektideks ja keerukamate algoritmide õppimiseks.