C Program to Check if a number is prime or not.

In this article, we are going to learn how to check whether a number is prime or not using C programming. Before we write code for this problem, we first need to understand prime numbers.

What is a Prime Number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In simpler terms, a prime number is a number that cannot be divided evenly by any other number except for 1 and itself. 

For example, 2, 3, 5, 7, 11, 13, 17, and 19 are all prime numbers.

There are multiples way to check whether a number is prime or not and here we are going to learn a few of those methods and also write C code for their implementation.

Approach 1: Basic Trial Division Method.

In this approach, we will check if the given number is divisible by any integer from 2 to the square root of the number. If we find any divisor, the number is not prime; otherwise, it is prime.

Step-by-step algorithm:

Step 1: Get the integer input that you want to check for prime.

Step 2: Check the two base cases, if the input value is less than or equal to 1 then it is not a prime number.

Step 3: Calculate the square root of the input number and round it to the nearest integer. Let's call this value "sqrt_num."

Step 4: Start a loop from 2 to "sqrt_num" (inclusive). For each integer "i" in the loop:

• Check if the input number is divisible by "i" (i.e., input number % i == 0).
• If it is divisible, the input number is not a prime number. Return "Not Prime."

Step 5: If the loop completes without finding any divisors (i.e., the input number is not divisible by any number from 2 to "sqrt_num"), then the input number is a prime number. Return "Prime."

C Code Implementation:

//C Program to check prime number
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime_basic(int num) {
    // Numbers less than or equal to 1 are not prime
    if (num <= 1) {
        return false; 
    }

    int sqrt_num = (int)sqrt(num);
    for (int i = 2; i <= sqrt_num; i++) {
        // Found a divisor, not a prime number
        if (num % i == 0) {
            return false; 
        }
    }
    // No divisors found, the number is prime
    return true; 
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    if (is_prime_basic(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Output:

Enter a positive integer: 5
5 is a prime number.

Time Complexity: O(sqrt(n))

Space Complexity: O(1)

Approach 2: Optimized Trial Division Method.

In this approach, we can make some optimizations to the basic trial division method. We will check if the number is divisible by 2 or 3, and then check for divisors starting from 5, skipping multiples of 2 and 3.

Step-by-step algorithm:

Step 1: Get the integer number that you want to check for primality.

Step 2: Check the base cases:

• If the input number is less than or equal to 1, it is not a prime number.
• If the input number is 2 or 3, it is a prime number. Return "Prime."

Step 3: If the input number is divisible by 2 or 3, it is not a prime number. Return "Not Prime."

Step 4: Calculate the square root of the input number and round it to the nearest integer. Let's call this value "sqrt_num."

Step 5: The code starts a loop from 5 to "sqrt_num" (inclusive) with a step size of 6. This is an optimization to check only certain potential divisors, which are 5 and 7 (since 5 + 2 = 7).

• For each value of "i" in the loop, it checks if the input number is divisible by "i" or "i + 2" using the modulo operator (%).
• If the input number is divisible by "i" or "i + 2," it means the number is not a prime, and the function returns "false."

Step 6: If the loop completes without finding any divisors (i.e., the input number is not divisible by any number in the optimized set of potential divisors), then the input number is a prime number.

C Code Implementation:

//C Program to check if a number is prime or not
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime_optimized(int num) {
    // Numbers less than or equal to 1 are not prime
    if (num <= 1) {
        return false; 
    }
    // 2 and 3 are prime numbers
    if (num <= 3) {
        return true; 
    }
    // Numbers divisible by 2 or 3 are not prime
    if (num % 2 == 0 || num % 3 == 0) {
        return false; 
    }

    int sqrt_num = (int)sqrt(num);
    for (int i = 5; i <= sqrt_num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false; // Found a divisor, not a prime number
        }
    }
    // No divisors found, the number is prime
    return true; 
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    if (is_prime_optimized(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Output:

Enter a positive integer: 17
17 is a prime number.

Time Complexity: O(sqrt(n))

Space Complexity: O(1)

Approach 3: Check Prime Number using Wilson’s Theorem.

Wilson's Theorem is a mathematical theorem that provides a condition for a positive integer "p" to be prime. According to Wilson's Theorem, "p" is a prime number if and only if (p - 1)! ≡ -1 (mod p), where "!" represents the factorial operation and "≡" denotes congruence.

Step-by-step algorithm:

Step 1: Input a positive integer "num" that you want to check for primality.

Step 2: If the value of "num" is less than or equal to 1, it is not a prime number. Return false.

Step 3: If "num" is 2 or 3, it is a prime number. Return true.

Step 4: Check if "num" is divisible by 2 or 3. If it is, it is not a prime number. Return false.

Step 5: Calculate the factorial of "num - 1" using a loop and the factorial function.

• The factorial function multiplies all integers from 2 to "num - 1" to calculate the factorial value.

Step 6: Check if (num - 1)! + 1 is divisible by "num" using the modulo operator.

• If (num - 1)! + 1 is congruent to 0 modulo "num," then "num" satisfies Wilson's Theorem, and it is a prime number. Return true.

Step 7: If (num - 1)! + 1 is not divisible by "num," "num" does not satisfy Wilson's Theorem, and it is not a prime number. Return false.

C Code Implementation of Wilson's Theorem,

//C Program to check prime number using Wilson’s Theorem
#include <stdio.h>

// Function to calculate the factorial of a number
int factorial(int num) {
    // Factorial of 0 and 1 is 1
    if (num == 0 || num == 1) {
        return 1; 
    }

    int result = 1;
    // Calculate the factorial
    for (int i = 2; i <= num; i++) {
        result *= i; 
    }

    return result;
}

// Function to check if a number is prime using Wilson's Theorem
int is_prime_wilson(int num) {
    // Numbers less than or equal to 1 are not prime
    if (num <= 1) {
        return 0; 
    }

    // Check if (num - 1)! ≡ -1 (mod num)
    if ((factorial(num - 1) + 1) % num == 0) {
        return 1; // The number satisfies Wilson's Theorem, it is prime
    } else {
        return 0; // The number does not satisfy Wilson's Theorem, it is not prime
    }
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    if (is_prime_wilson(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Output:

Enter a positive integer: 7
7 is a prime number.

Time Complexity: O(n)

Space Complexity: O(1)

Note: Wilson's Theorem is not practical for large numbers as the factorial operation becomes computationally expensive.(alert-passed)

C Program to Add Two Integer Number.

Adding two integer numbers is one of the fundamental operations in any programming language, including C. To add two integer numbers we use the addition operator (+) and store the result in another integer variable. To learn this program you must basic understanding of input and output operators in C Programming.

Step-by-step algorithm for Addition:

Step 1: Declare three variables, num1, num2, and sum.

Step 2: Take user input for values of num1 and num2 and store it in the variables.

Step 3: Add the value of num1 and num2 and store the result in the variable sum.

Step 4: Display the value of the sum as a result. 

Step 5: End the program.

C Code to Add Two Integer values.

//C Program to add two Integer number
#include <stdio.h>

int main() {
    // Step 1: Declare variables
    int num1, num2, sum;

    // Step 2: Input first number
    printf("Enter the first integer: ");
    scanf("%d", &num1);

    // Step 3: Input second number
    printf("Enter the second integer: ");
    scanf("%d", &num2);

    // Step 4: Perform the addition
    sum = num1 + num2;

    // Step 5: Display the result
    printf("The sum of %d and %d is %d.\n", num1, num2, sum);

    return 0;
}

Output:

Enter the first integer: 10
Enter the second integer: 5
The sum of 10 and 5 is 15.

• Time Complexity: O(1)
• Space Complexity: O(1)

C Program Input/Output Operation.

We use a C programming language to communicate with computers to solve problems and once we get our required output we need to show them on the output screen. There might of some cases in which we also take input data from the user itself. Here we are going to understand how to take input and print output of our console screen.

How to take Input/Output in C Programming?

The two important functions printf and scanf are used in the C programming language to perform output and input operations. Let's understand both in detail with examples.

Note: We need to include <stdio.h> header file at the top because both input and output functions are present inside this header file. (alert-success)

printf function.

The printf function is used for formatted output in C. It allows you to print text and values to the console in a specific format.

Example Code: 

//C Program to show the working of printf function
#include <stdio.h>

int main() {
    int age = 25;
    float height = 5.9;
    char name[] = "John Doe";

    // Printing variables with format specifiers
    printf("Name: %s\n", name);
    printf("Age: %d\n", age);
    printf("Height: %.2f\n", height);

    return 0;
}

Output:

Name: John Doe
Age: 25
Height: 5.90

In this example, the printf function is used to print the name, age, and height of a person using format specifiers. %s is used for strings, %d for integers, and %.2f for floating-point numbers with two decimal places.

scanf function.

The scanf function is used for formatted input in C. It allows you to read values from the user or a file based on the specified format. 

Example Code:

//C Program to take input from user
#include <stdio.h>

int main() {
    char name[50];
    int age;

    // Reading input from the user with format specifiers
    printf("Enter your name: ");
    scanf("%s", name);

    printf("Enter your age: ");
    scanf("%d", &age);

    // Displaying the input values
    printf("Name: %s\n", name);
    printf("Age: %d\n", age);

    return 0;
}

Output:

Enter your name: Algolesson
Enter your age: 5
Name: Algolesson
Age: 5

In this example, the scanf function is used to read the name and age of the user from the console using format specifiers %s and %d, respectively. Note that for reading integers, we need to pass the memory address of the variable using the & (address-of) operator.

Format Specifiers.

We notice that format specifiers are something that we should know. In C programming, format specifiers are used with input/output functions like printf and scanf to specify the data type and format of the variables being printed or read.

List of Format Specifiers in C Program.

• %d : Used for integers (decimal format).
• %ld : Used for long integers.
• %u : Used for unsigned integers.
• %f : Used for floating-point numbers (decimal notation).
• %lf : Used for double-precision floating-point numbers.
• %c : Used for characters.
• %s : Used for strings (arrays of characters).
• %x : Used for hexadecimal (lowercase letters).
• %X : Used for hexadecimal (uppercase letters).
• %o : Used for octal numbers.
• %% : Used to print a literal % character (escape sequence).

Note: Some format specifiers have variations for different data types, such as %lld for long long integers, %hu for unsigned short integers, etc. (alert-success)

Program to find third distinct maximum number in the array.

Given an integer array nums[] of size n, we need to find the third distinct maximum number in an integer array nums. If the third maximum number does not exist, we need to return the maximum number present in the array.

Note: If the array has less than three distinct maximum numbers, then we need to return the maximum number from the array.

Let's understand the problem with an example:

Example 1:
Input: nums[] = {3, 5, 1, 8, 5, 4, 2, 9}
Output: 5

Explanation: 

The distinct maximum numbers in the array are 9, 8, and 5. 
So, the third distinct maximum number is 5. 

Example 2:
Input: nums[] = {2, 8}
Output: 8

Explanation: 

No third element is present in the given array 
so return the maximum element that is 8

Example 3:
Input: nums[] = {2, 2, 3, 1}
Output: 1

Explanation: 

The distinct maximum numbers in the array are 3, 2, and 1. 

So, the third distinct maximum number is 1. 

There are multiple approaches by which we can solve this problem and here we are going to discuss each of them one by one.

Approach 1: Using Sorting.

The brute force approach to solve this problem is by arranging the given array in descending order which will make our task easier to find the third distinct element.

Steps-by-step algorithm:

Step 1: We can sort the array in descending order.

Step 2: Then, we can iterate through the sorted array and keep track of distinct maximum numbers.

Step 3: If we find the third distinct maximum number, we return it. Otherwise, we return the maximum number.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    //arrange the vector in descending order
    sort(nums.begin(), nums.end(), greater<int>());

    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            count++;
        }
        if (count == 3) {
            return nums[i];
        }
    }
    //return max if no third distinct max is found
    return nums[0];
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

5

Time Complexity: The sorting operation using sort takes O(n * log n) time, where n is the number of elements in the input array. After sorting, we iterate through the sorted array once to find the third distinct maximum number. This step takes O(n) time. So, the overall time complexity is O(n * log n + n) = O(n * log n).

Space Complexity: The space complexity is O(1) as we are not using any additional data structure. 

Approach 2: Using Set.

As we know a set container is used to store unique elements in a specific order and allows for efficient insertion, deletion, and retrieval of elements based on their values. 

Step-by-step algorithm:

Step 1: We can use a set to keep track of distinct numbers while traversing the array.

Step 2: If the set size is less than 3 after traversing the array, it means we have less than three distinct maximum numbers, so we return the maximum number present in the array.

Step 3: If the set size is greater than or equal to 3, we return the third element from the set.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum using set
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    set<int> distinctNums;

    //traverse the array and atmost
    //store three elements in the set
    for (int num : nums) {
        distinctNums.insert(num);
        if (distinctNums.size() > 3) {
            distinctNums.erase(distinctNums.begin());
        }
    }
    //size of set is less than 3 
    //no third distinct element present
    if(distinctNums.size() < 3)
    //return max element present in set
       return *(--distinctNums.end());
    //size of set is equal to 3 
    //top most element of set is the third distinct
    else
       return *(distinctNums.begin());
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

5

Note: The expression *(--distinctNums.end()) is used to access the last element in a set. 

Time Complexity: The set insertion and deletion operations have an average time complexity of O(log n) then we iterate through the entire input array once, performing set operations on each element, so the overall time complexity is O(n * log n).

Space Complexity: The space required for the set depends on the number of distinct elements in the array, which is at most 3 in this case. Therefore, the space complexity is O(1), as it remains constant regardless of the input size.

Approach 3: Using three variables. (Most Optimized).

The idea for this optimized approach comes from the requirement to find the third distinct maximum number in a single pass through the array with O(n) time complexity. To achieve this efficiently, we need to keep track of the first, second, and third distinct maximum numbers while traversing the array.

Step-by-step algorithm:

Step 1: We declare three variables (firstMax, secondMax, thirdMax) to keep track of the first, second, and third distinct maximum numbers, respectively.

Step 2: We initialize them with the minimum possible value (INT_MIN).

Step 3: We traverse the input array and update these variables as follows:

• If the current number is greater than firstMax, we update thirdMax with secondMax, secondMax with firstMax, and then update firstMax with the current number.
• If the current number is between firstMax and secondMax, we update thirdMax with secondMax and secondMax with the current number.
• If the current number is between secondMax and thirdMax, we update thirdMax with the current number.

Step 4: After the loop, if thirdMax remains equal to the initial value (INT_MIN), it means there are less than three distinct maximum numbers in the array, and we return firstMax (the maximum number). Otherwise, we return thirdMax.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <bits/stdc++.h>
using namespace std;

int thirdMax(vector<int>& nums) {
    int firstMax = INT_MIN;
    int secondMax = INT_MIN;
    int thirdMax = INT_MIN;

    for (int num : nums) {
        //current number is greater
        if (num > firstMax) {
            thirdMax = secondMax;
            secondMax = firstMax;
            firstMax = num;
        } 
        //current number is between first and second max
        else if (num < firstMax && num > secondMax) {
            thirdMax = secondMax;
            secondMax = num;
        } 
        //current number is between second and third max
        else if (num < secondMax && num > thirdMax) {
            thirdMax = num;
        }
    }

    return (thirdMax == INT_MIN) ? firstMax : thirdMax;
}


int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2};

    cout<< thirdMax(nums);

    return 0;
}

Output:

4

Time Complexity: The time complexity of this solution is O(n) as we are able to find the required answer just in a single traversal. 

Space Complexity: The space complexity is constant O(1) as we are only using three variables for solving this problem. 

I hope you are able to understand all three approaches to solving this problem. We have covered all three approaches in sequence order from brute force to optimized one.  

Hello World Program in C.

The "Hello World" program is a traditional introductory program that displays the text "Hello, World!" on the screen. While it may seem straightforward, this program encompasses key programming concepts like input/output and syntax, making it an ideal starting point for beginners who want to learn C Programming.

Working of the C Hello World Program.

To create a "Hello World" program in C, follow these simple steps:

Step 1: Setting up the Development Environment.

Before you begin, ensure you have a C compiler installed on your system. Popular choices include GCC (GNU Compiler Collection) for Linux and MinGW for Windows. Once you have the compiler installed, you're ready to start coding.

Step 2: Writing the C Code.

Open a text editor and create a new file. Begin by including the standard input/output header file "stdio.h," which provides functions for input and output operations. Within the main function, add the printf function to display the "Hello, World!" message on the screen.

C Example:

#include <stdio.h>

int main() {

    printf("Hello, World!");

    return 0;
}

Output:

Hello, World!

Step 4: Save and Compile the Program.

Save the file with a .c extension, such as hello_world.c. Open your terminal or command prompt, navigate to the file's location, and compile the program using the C compiler:

For GCC on Linux:

gcc -o hello_world hello_world.c

For MinGW on Windows:

gcc -o hello_world.exe hello_world.c

Step 5: Running the Program.

After successful compilation, you will see an executable file in the same directory as your C file. 

Run the program by typing the following command:

For Linux:

./hello_world

For Windows:

hello_world.exe

Congratulations! You have just created and executed your first C Hello World program. I hope you now understand the basic working of the C Program and how to execute it. 

(getButton) #text=(C Program Input/Output Operation.) #icon=(link) #color=(#2339bd)

How To Initialize a Vector in C++? (5 Different Ways)

In C++, a vector is a dynamic array-like data structure provided by the Standard Template Library (STL). It allows the storage of elements of the same type in a contiguous memory block and provides dynamic resizing, allowing elements to be added or removed efficiently.

Vectors also support random access to elements and offer a variety of useful member functions for manipulation and iteration. There are multiple ways to initialize a vector and here we are going to see 5 different ways to do so. Let's learn each of them one by one.

1. Initializing with Initializer List: 

It is very much similar to initializing an array data structure using curly brackets and the size of the vector is decided based on the number of elements present. 

//C++ Program to initialize vector using initializer
#include<iostream>
#include<vector>
using namespace std;

int main(){

    vector<int> nums = {1, 2, 3, 4, 5};

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

1 2 3 4 5

2. Initializing using push_back() function: 

It is a built-in function present in the vector used to push the element at the end. Read more to know about vector built-in functions.

//C++ Program to initialize vector one by one
#include<iostream>
#include<vector>
using namespace std;

int main(){

    vector<int> nums;

    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(8);
    nums.push_back(0);

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

1 2 8 0

3. Initializing with Size and Default Value: 

Here we are declaring two values while creating the vector, the first value defines the size of the vector, and the second value is the default value assigned to all the elements.

//C++ Program to initialize vector by default value
#include<iostream>
#include<vector>
using namespace std;

int main(){

    //vector of size 5 with all elements initialized to 0
    vector<int> nums(5, 0);

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

0 0 0 0 0

4. Initializing with Range of Elements:

Here we are using one vector to initialize a new vector with the same elements.

//C++ Program to initialize one vector using another vector
#include<iostream>
#include<vector>
using namespace std;

int main(){

    vector<int> nums{7, 2, 3, 1, 5};
    // Create a new vector with the same elements as nums
    vector<int> copyNums(nums.begin(), nums.end()); 

    for(int it : copyNums){
        cout<< it << " ";
    }

    return 0;
}

Output:

7 2 3 1 5

5. Initializing with Array:

Here, in this case, we are going to use the array to initialize a vector. For this, we must know the size of the given array. We have calculated the size using sizeof() function. 

 

//C++ Program to initialize one vector using array
#include<iostream>
#include<vector>
using namespace std;

int main(){

    int arr[] = {1, 2, 3, 4, 5};
    //size of given array
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> nums(arr, arr + n);

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

7 2 3 1 5

So these are the few different ways in which we can initialize a vector. All these initialization is performed within O(n) time complexity.