Prime numbers have a major role in both computer science and mathematics. These unique integers, divisible only by 1 and themselves, have fascinated scholars, programmers, and mathematicians for centuries. If you’re seeking to unravel the mysteries of prime numbers using C++, you’ve come to the right place. In this blog post, we’ll explore various program related to print prime numbers in C++, along with their time and space complexities. Brace yourself for a journey through the realm of prime numbers!

## What is Prime Number ?

A prime number is a natural number higher than 1 that has just itself and the number 1 as its only other positive divisors. In other terms, a prime number is one that can only be divided evenly by itself and by 1 and no other number. Since they only have the number itself and the divisor 1, prime numbers like 2, 3, 5, 7, 11, and 13 are only divisible by these two numbers. However, because they have divisors besides 1 and themselves (for instance, 4 is divisible by 2), integers like 4, 6, 8, and 9 are not prime. along with several uses in mathematics, computer science, and encryption, prime numbers play a crucial role in number theory.In the below table we listed the Prime and non prime numbers upto 100:

## Algorithm for checking number is prime or not

- Use the variable i to start a loop that goes from 2 to n/2.
- Utilise the modulo operator (n% i == 0) inside the loop to determine whether n is divisible by i.
- N is a prime number if it cannot be divided by i.
- If n has divisors other 1 and itself, then it is not a prime number since n is divisible by i.

## Program to check number is prime or not

### FIrst Logic : A Simple Approach

```
#include <iostream>
using namespace std;
bool isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
int number;
cout << "Enter a positive integer: ";
cin >> number;
if (isPrime(number)) {
cout << number << " is a prime number." << endl;
} else {
cout << number << " is not a prime number." << endl;
}
return 0;
}
```

If you want to run code and check output, you can use this online C++ compiler

**Output **:

###### - Advertisement -

```
Enter a positive integer: 17
17 is a prime number.
for other positive value :
Enter a positive integer: 15
15 is not a prime number.
```

### Complexity of the code

**Time Complexity**: O(√n), where n is the input number.**Space Complexity**: O(1), constant space.

### Second Logic : Alternative logic for checking prime number in C++

```
#include <iostream>
using namespace std;
bool isPrime(int num) {
if (num <= 1) {
return false;
}
if (num <= 3) {
return true;
}
if (num % 2 == 0 || num % 3 == 0) {
return false;
}
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
int number;
cout << "Enter a positive integer: ";
cin >> number;
if (isPrime(number)) {
cout << number << " is a prime number." << endl;
} else {
cout << number << " is not a prime number." << endl;
}
return 0;
}
```

If you want to run code and check output, you can use this online C++ compiler

**Output :**

```
Enter a positive integer: 29
29 is a prime number.
and
Enter a positive integer: 15
15 is not a prime number.
```

### Complexity of the code

**Time Complexity**: O(√n), where n is the input number.**Space Complexity**: O(1), constant space.

Also Read This :

Operating system projects with source code | operating system micro project topics free download

Software testing micro projects proposal and report pdf free download

###### - Advertisement -

Javascript micro projects with source code free download

## Optimized Approach : C++ Program to Print Prime Numbers in range

For scenarios where the limit of prime numbers to be generated is significantly larger, the Segmented Sieve offers an efficient alternative. By dividing the range into segments and sieving each segment individually, this approach strikes a balance between time and space complexity. Its time complexity is O(n log n), and space complexity remains O(sqrt(n)).

```
#include <iostream>
#include <vector>
void segmentedSieve(int low, int high) {
std::vector<bool> isPrime(high - low + 1, true);
std::vector<int> primes;
for (int p = 2; p * p <= high; ++p) {
for (int i = std::max(p * p, (low + p - 1) / p * p); i <= high; i += p) {
isPrime[i - low] = false;
}
}
for (int i = low; i <= high; ++i) {
if (isPrime[i - low]) {
primes.push_back(i);
}
}
std::cout << "Prime numbers between " << low << " and " << high << ": ";
for (int prime : primes) {
std::cout << prime << " ";
}
}
int main() {
int lower, upper;
std::cout << "Enter lower and upper limits: ";
std::cin >> lower >> upper;
segmentedSieve(lower, upper);
return 0;
}
```

**Output**:

###### - Advertisement -

```
Enter lower and upper limits: 1 20
Prime numbers between 1 and 20: 1 2 3 5 7 11 13 17 19
```

### Complexity of the code

**Time Complexity**: O(n * ln(sqrt(n))) , where n is the input number.**Space Complexity**: O(sqrt(n)), where n is the input number.

## Conclusion

In the context of programming , the ability to craft efficient prime number programs is a hallmark of skill and expertise. By mastering the naïve approach, Sieve of Eratosthenes, and the segmented sieve, you’ve equipped yourself with a versatile arsenal of techniques to generate prime numbers in C++. Remember, selecting the right approach depends on the specific requirements of your project. Real time applications for prime number programmes and the prime number notation exist in multiple areas. Here are a few instances:

- Algorithms and Code Optimization
- Hashing and Data Structures
- Random Number Generation
- Cryptography and Security.

**Read This Also**

**If you have any questions or need further clarification on any of the projects, feel free to ask.** Our team is here to help you out! Are there any other micro projects you’d like to see in future articles? Let us know, and we’ll be delighted to create more exciting content for you. Your feedback is valuable to us, and we look forward to hearing from you. Let’s engage in constructive discussions and learn together as a community.