View this post on Instagram

A post shared by Vasanta Kumar | Software Engineer 🧑‍💻 (@gurucodes.dev)

Prime numbers are whole numbers greater than 1 that have exactly two factors: 1 and themselves.

In other words, a prime number cannot be evenly divided by any other number except 1 and itself. For example, 7 is a prime number because the only factors of 7 are 1 and 7. On the other hand, 4 is not a prime number because it has factors other than 1 and 4 (namely, 2 and 4).

Prime numbers are essential in number theory and have many applications in cryptography, coding theory, and other fields.

Here are some of the first few prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Here’s how to check if a number is prime in C++ using both the naive and optimized methods:

1. Naive Method:

#include <iostream>

bool is_prime_naive(int num) {
  if (num <= 1) {
    return false;
  }
  for (int i = 2; i <= sqrt(num); ++i) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  int number;
  std::cout << "Enter a number: ";
  std::cin >> number;

  if (is_prime_naive(number)) {
    std::cout << number << " is a prime number." << std::endl;
  } else {
    std::cout << number << " is not a prime number." << std::endl;
  }

  return 0;
}

Explanation:

• We define a function is_prime_naive that takes an integer as input.
• Inside the function, we check if the number is less than or equal to 1, as those are not prime.
• We then loop through all integers from 2 to the square root of the number.
• For each value, we check if the number is divisible by the current divisor using the modulo operator (%). If it is divisible, we return false because it has a factor other than 1 and itself.
• If we loop through all divisors without finding any, the number is prime and we return true.
• In the main function, we get the user input and call the is_prime_naive function to check if the number is prime. We then print the result.

2. Optimized Method:

#include <iostream>

bool is_prime_optimized(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;
  std::cout << "Enter a number: ";
  std::cin >> number;

  if (is_prime_optimized(number)) {
    std::cout << number << " is a prime number." << std::endl;
  } else {
    std::cout << number << " is not a prime number." << std::endl;
  }

  return 0;
}

Explanation:

• This method skips unnecessary checks by taking advantage of the properties of prime numbers.
• We initially perform basic checks for 2 and 3 as they are the only even prime numbers.
• We then loop through odd divisors starting from 5 and incrementing by 6 (to skip even numbers).
• We also check both i and i + 2 as consecutive odd numbers cannot both be factors of an odd number.
• If any divisibility is found, we return false. Otherwise, we return true at the end of the loop.

Key Points:

The optimized method is faster for larger numbers.

Both methods have a time complexity of O(sqrt(n)).

You can choose the method that best suits your needs based on the expected range of numbers and performance requirements.

Or you can also choose to use Fermat’s little theorem, Miller rabins primality test, etc. for finding out whether a number is prime or not.

I hope this explanation is helpful! Let me know if you have any further questions.