Prime numbers are interesting area to research. A prime number, it is also called prime shortly , is a natural number (a positive integer) greater than 1 that is not a product of two smaller natural numbers. If a number is not prime then it is called as a composed number. There are several mathematical questions regarding prime numbers are still unsolved. Finding them and relations and their effects on some other functions, graphics really interesting in mathematical phenomena.
Calculating prime numbers in a range is another comparison in programming languages. C++ is the fastest and most powerful programming language and it is easy to calculate prime numbers. In this post, we will explain how to find Prime Numbers in C++ Builder. C++ Builder is a great IDE, includes compilers for Windows, Android and iOS. C++Builder has both CLANG Enhanced C/C++ Compiler and a Borland C/C++ Compiler. You can download the free C++ Builder Community Edition here: https://www.embarcadero.com/products/cbuilder/starter. Professional developers can use the Professional, Architect or Enterprise versions of C++ Builder. Please visit https://www.embarcadero.com/products/cbuilder.
Now, lets start to find if a given number is prime or not. To do this, we will create our own prime number .
|
1 2 3 4 5 6 7 8 9 10 11 |
bool is_prime0(unsigned int x) { if(x<=1) return(false); for(unsigned int i=2; i<=x; i++) { if((x%i)==0) return(false); } return(true); } |
This function is counting all number and may be slower, we don’t need to count all of them. Trial division is the most laborious but easiest to understand of the integer factorization algorithms, it is well used to define maximum search number of prime numbers.. We can enhance and speed up this procedure by this method. We limit our for loop with q variable which is calculated with this method. By adding this, it will be as below;
|
1 2 3 4 5 6 7 8 9 10 |
bool is_prime(unsigned int x) { if(x<=1) return(false); unsigned int q = floor(sqrt(x)); for(unsigned int i=2; i<=q; i++) { if((x%i)==0) return(false); } return(true); } |
We can say that this procedure above is the most simple to calculate if a number is a prime number or not. Note that unsigned integer ranges 0 to 4,294,967,295. For larger number you need to use double long or you may need more specific procedures for more higher numbers.
Now lets count all numbers in a given range (from 2 to maxN) by using our is_prime() function.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int count_primes(unsigned int maxN) { unsigned int res=0; for(int i=2; i<=maxN; i++) { if(is_prime(i)) res++; } return(res); } |
Finally, we can easily calculate number of primes in a given range as below;
|
1 2 3 4 5 6 7 8 9 |
#define max_n 1000000 // we need to define this above the procedures void __fastcall TForm1::Button1Click(TObject *Sender) { count = count_primes(max_n); Memo1->Lines->Add(L"Number of primes between "+IntToStr(max_n)+L"= "+UIntToStr(count) ) ; } |
In summary, create a new Multi-Device C++ Builder Project in C++ Builder, add a Button and a Memo components to see output. All all codes should be as below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
//--------------------------------------------------------------------------- #include <fmx.h> #pragma hdrstop #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.fmx" TForm1 *Form1; //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- #define max_n 1000000 //--------------------------------------------------------------------------- bool is_prime(unsigned int x) { if(x<=1) return(false); unsigned int q = floor(sqrt(x)); for(unsigned int i=2; i<=q; i++) { if((x%i)==0) return(false); } return(true); } //--------------------------------------------------------------------------- int count_primes(unsigned int maxN) { unsigned int res=0; for(int i=2; i<=maxN; i++) { if(is_prime(i)) res++; } return(res); } //--------------------------------------------------------------------------- void __fastcall TForm1::Button1Click(TObject *Sender) { count = count_primes(max_n); Memo1->Lines->Add(L"Number of primes between "+IntToStr(max_n)+L"= "+UIntToStr(count) ) ; } //--------------------------------------------------------------------------- |
