Prime Number Program in C++

A number n is said to be prime if it is not divisible by any number other than 1 and the number n itself. Examples of prime numbers are 2, 13, 19, etc. Examples of non-prime numbers are 1, 0, 4, 6, etc. In this article, we will look at the Prime Number Program in C++.

Algorithm to Check Prime Numbers in C++

Now, we will learn the Algorithm to find Prime Number in C++.

1. Start with the number num you want to check for primality.
2. If num is less than or equal to 1, it's not prime.
3. If num is 2, it's a prime number.
4. If num is even (except 2), it's not prime.
5. Otherwise, loop through odd numbers from 3 up to the square root of num.
   • If num is divisible by any of these odd numbers, it's not prime.
6. If no divisor is found in the above step, num is prime.

Prime Number Program in C++

Let's learn how to write Prime Number Program in C++.

Explanation of Prime number code for C++:

• The isPrime() function takes an integer num as input and returns true if num is prime and false otherwise.
• It first checks if the number is less than or equal to 1, in which case it's not prime.
• Then, it iterates from the 2 to the square root of num, checking if num is divisible by any number in this range.
• If it finds any divisor, it returns false, indicating that the number is not prime.
• If no divisor is found, it returns true, indicating that the number is prime.

In the main() function, the user is prompted to input a number, and then the isPrime() function is called to check if the number is prime or not, and the result is printed accordingly.

Complexity Analysis

Time complexity

• The time complexity to check prime number in C++ is O(sqrt(num)).
• It iterates through numbers up to the square root of the input number to determine its primality.

Space Complexity

• The algorithm doesn't use any additional data structures that grow with the input size.
• It only uses a constant amount of extra space for variables like num and i.
• Therefore, the space complexity is O(1), constant space.

To summarize:

• Time Complexity: O(sqrt(num))
• Space Complexity: O(1)**