primarni brojevi oduvijek su fascinirali matematičare i nematematičare. Prosti broj je cijeli broj veći od 1 koji nema djelitelja osim 1 i samog sebe. Proces određivanja da li je broj prost ili ne je uobičajen problem u programiranju i matematičkim proračunima. U ovom članku ćemo se fokusirati na funkciju isPrime u C++ koji se koristi za određivanje da li je dati broj prost ili ne.
The isPrime funkcija ima jasnu logiku. Prihvata cijeli broj kao parametar i provjerava da li broj ima bilo koje djelitelje osim 1 i samog sebe. To radi tako što pokušava podijeliti broj sa svim cijelim brojevima manjim od njega i većim od 1. Ako pronađe bilo koje druge djelitelje, vraća netačno, što ukazuje da broj nije prost. Ako se ne pronađu djelitelji, vraća true, što pokazuje da je broj prost.
C++ kod za funkciju je ispod:
bool isPrime(int n) {
if (n <= 1) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } [/code]
Objašnjenje rješenja
Prvi red funkcije provjerava da li je ulazni broj n manji ili jednak 1. Ako je tako, odmah vraća false jer po definiciji prost broj mora biti veći od 1.
Funkcija tada izvršava petlju for gdje je varijabla petlje i u rasponu od 2 do n-1. Na svakoj iteraciji, funkcija provjerava da li je n djeljivo sa i pomoću operacije modula. Operacija 'n % i' vraća ostatak dijeljenja n sa i. Ako u bilo kojoj tački vrati 0, to znači da je n potpuno deljivo sa i, pa stoga n nije prosto. U ovom trenutku, funkcija odmah vraća false.
Biblioteke i funkcije uključene u izračunavanje prostih brojeva
Iako je isPrime funkcija ne zahtijeva nikakve posebne biblioteke za rad, druge matematičke funkcije i koncepti u C++-u mogu biti od pomoći za složenije testove primarnosti ili druge probleme teorije brojeva.
C++ standardne biblioteke:
- cmath biblioteka: ima nekoliko funkcija korisnih za matematičke proračune kao što su snaga, kvadratni korijen, itd. koje bi mogle biti od pomoći u operacijama u vezi s prostim brojevima.
- Biblioteka limita: pomaže u rukovanju najvećim ili najmanjim brojevima koji se mogu pohraniti u cjelobrojne varijable što bi moglo biti korisno kada se radi s velikim prostim brojevima.
Napredni Primality Test:
Napredni test primarnosti poput Miller-Rabin ili AKS mogao bi se koristiti za rješavanje velikih brojeva. Ali ovi algoritmi zahtijevaju razumijevanje teorije brojeva.
Stoga, programiranje prostim brojevima isprepliće i moć matematike i programiranja za rješavanje zamršenih problema na sistematski način.
