C++ Programming Code Examples
C++ > Data Structures and Algorithm Analysis in C++ Code Examples
Randomized primality testing algorithm, with a test program
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/* Randomized primality testing algorithm, with a test program */
#include <iostream.h>
#include "Random.h"
typedef int HugeInt;
/**
* Method that implements the basic primality test.
* If witness does not return 1, n is definitely composite.
* Do this by computing a^i (mod n) and looking for
* non-trivial square roots of 1 along the way.
*/
HugeInt witness( const HugeInt & a, const HugeInt & i, const HugeInt & n )
{
if( i == 0 )
return 1;
HugeInt x = witness( a, i / 2, n );
if( x == 0 ) // If n is recursively composite, stop
return 0;
// n is not prime if we find a non-trivial square root of 1
HugeInt y = ( x * x ) % n;
if( y == 1 && x != 1 && x != n - 1 )
return 0;
if( i % 2 != 0 )
y = ( a * y ) % n;
return y;
}
/**
* The number of witnesses queried in randomized primality test.
*/
const int TRIALS = 5;
/**
* Randomized primality test.
* Adjust TRIALS to increase confidence level.
* n is the number to test.
* If return value is false, n is definitely not prime.
* If return value is true, n is probably prime.
*/
bool isPrime( const HugeInt & n )
{
Random r;
for( int counter = 0; counter < TRIALS; counter++ )
if( witness( r.randomInt( 2, (int) n - 2 ), n - 1, n ) != 1 )
return false;
return true;
}
int main( )
{
for( int i = 101; i < 200; i += 2 )
if( isPrime( i ) )
cout << i << " is prime" << endl;
return 0;
}
#include is a way of including a standard or user-defined file in the program and is mostly written at the beginning of any C/C++ program. This directive is read by the preprocessor and orders it to insert the content of a user-defined or system header file into the following program. These files are mainly imported from an outside source into the current program. The process of importing such files that might be system-defined or user-defined is known as File Inclusion. This type of preprocessor directive tells the compiler to include a file in the source code program.
The cout is a predefined object of ostream class. It is connected with the standard output device, which is usually a display screen. The cout is used in conjunction with stream insertion operator (<<) to display the output on a console. On most program environments, the standard output by default is the screen, and the C++ stream object defined to access it is cout. The "c" in cout refers to "character" and "out" means "output". Hence cout means "character output". The cout object is used along with the insertion operator << in order to display a stream of characters.
As the name already suggests, these operators help in assigning values to variables. These operators help us in allocating a particular value to the operands. The main simple assignment operator is '='. We have to be sure that both the left and right sides of the operator must have the same data type. We have different levels of operators. Assignment operators are used to assign the value, variable and function to another variable. Assignment operators in C are some of the C Programming Operator, which are useful to assign the values to the declared variables. Let's discuss the various types of the assignment operators such as =, +=, -=, /=, *= and %=. The following table lists the assignment operators supported by the C language:
The C++ comments are statements that are not executed by the compiler. The comments in C++ programming can be used to provide explanation of the code, variable, method or class. If we write comments on our code, it will be easier for us to understand the code in the future. Also, it will be easier for your fellow developers to understand the code. By the help of comments, you can hide the program code also. There are two types of comments in C++: • Single Line comment. • Multi Line comment
A program shall contain a global function named main, which is the designated start of the program in hosted environment. main() function is the entry point of any C++ program. It is the point at which execution of program is started. When a C++ program is executed, the execution control goes directly to the main() function. Every C++ program have a main() function.
A relational operator is used to check the relationship between two operands. C++ Relational Operators are used to relate or compare given operands. Relational operations are like checking if two operands are equal or not equal, greater or lesser, etc. Relational Operators are also called Comparison Operators.
Logical Operators are used to compare and connect two or more expressions or variables, such that the value of the expression is completely dependent on the original expression or value or variable. We use logical operators to check whether an expression is true or false. If the expression is true, it returns 1 whereas if the expression is false, it returns 0. Assume variable A holds 1 and variable B holds 0:
Arithmetic Operator is used to performing mathematical operations such as addition, subtraction, multiplication, division, modulus, etc., on the given operands. For example: 6 + 3 = 9, 5 - 3 = 2, 3 * 4 = 12, etc. are the examples of arithmetic operators. Let's discuss the different types of Arithmetic Operators in the C programming. Plus Operator is a simple Plus (+) Operator used to add two given operands. We can use Plus Operator with different data types such as integer, float, long, double, enumerated and string type data to add the given operand. The minus operator is denoted by the minus (-) symbol. It is used to return the subtraction of the first number from the second number. The data type of the given number can be different types, such as int, float, double, long double, etc., in the programing language.
In computer programming, loops are used to repeat a block of code. For example, when you are displaying number from 1 to 100 you may want set the value of a variable to 1 and display it 100 times, increasing its value by 1 on each loop iteration. When you know exactly how many times you want to loop through a block of code, use the for loop instead of a while loop. A for loop is a repetition control structure that allows you to efficiently write a loop that needs to execute a specific number of times.
A return statement ends the processing of the current function and returns control to the caller of the function. A value-returning function should include a return statement, containing an expression. If an expression is not given on a return statement in a function declared with a non-void return type, the compiler issues an error message. If the data type of the expression is different from the function return type, conversion of the return value takes place as if the value of the expression were assigned to an object with the same function return type.
In computer programming, we use the if statement to run a block code only when a certain condition is met. An if statement can be followed by an optional else statement, which executes when the boolean expression is false. There are three forms of if...else statements in C++: • if statement, • if...else statement, • if...else if...else statement, The if statement evaluates the condition inside the parentheses ( ). If the condition evaluates to true, the code inside the body of if is executed. If the condition evaluates to false, the code inside the body of if is skipped.
Here, we use 'swapping' of the elements with the help of a Variable say temp of same type. That is, on found, start 'Swapping' with temp variable, place the first number in the temp &
The factorial of a positive integer n is equal to 1*2*3*...n. In program, user enters a positive integer. Then the "factorial" of that number is "computed and displayed" in the screen. Here
Program to find the connected components of the "undirected graph". This can be done using depth first search. Implementation of "Kosaraju's algorithm" to print all SCCs. Fills
