Prime Numbers

A prime number is a whole number greater than 1, which is only divisible by 1 and itself. First few prime numbers are : 2 3 5 7 11 13 17 19 23 …..

Some interesting fact about Prime numbers

1. Two is the only even Prime number.
2. Every prime number can represented in form of 6n+1 or 6n-1 except 2 and 3, where n is natural number.
3. Two and Three are only two consecutive natural numbers which are prime too.
4. Goldbach Conjecture: Every even integer greater than 2 can be expressed as the sum of two primes.
5. GCD of all other natural numbers with a prime is always one.
6. Wilson Theorem : Wilson’s theorem states that a natural number p > 1 is a prime number if and only if

       (p - 1) ! ≡  -1   mod p 
   OR  (p - 1) ! ≡  (p-1) mod p

7. Fermat’s Little Theorem: If n is a prime number, then for every a, 1 <= a < n,

   an-1 ≡ 1 (mod n)
    OR 
   an-1 % n = 1 

8. Prime Number Theorem : The probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or to the logarithm of n.
9. Lemoine’s Conjecture : Any odd integer greater than 5 can be expressed as a sum of an odd prime (all primes other than 2 are odd) and an even semiprime. A semiprime number is a product of two prime numbers. This is called Lemoine’s conjecture.

How we check whether a number is Prime or not?

1. Naive solution.
   A naive solution is to iterate through all numbers from 2 to n-1 and for every number check if it divides n. If we find any number that divides, we return false.
   

   C++

   
   
   

   // A school method based C++ program to  // check if a number is prime #include <bits/stdc++.h> using namespace std;    // function check whether a number  // is prime or not bool isPrime(int n) {     // Corner case     if (n <= 1)         return false;        // Check from 2 to n-1     for (int i = 2; i < n; i++)         if (n % i == 0)             return false;        return true; }    // Driver Program int main() {     isPrime(11) ? cout << " true " :                    cout << " false ";     return 0; }

   Java

   // A school method based Java program to  // check if a number is prime import java.util.*;    class GFG {            // function check whether a number      // is prime or not     static boolean isPrime(int n)     {         // Corner case         if (n <= 1)             return false;                 // Check from 2 to n-1         for (int i = 2; i < n; i++)             if (n % i == 0)                 return false;                 return true;     }            /* Driver program  */     public static void main(String[] args)      {          if(isPrime(11))           System.out.println(" true") ;                     else           System.out.println(" false");                 } }        // This code is contributed by Arnav Kr. Mandal

   Python3

   # A school method based Python3 program  # to check if a number is prime    # function check whether a number  # is prime or not def isPrime(n):            # Corner case     if (n <= 1):         return False        # Check from 2 to n-1     for i in range(2, n):         if (n % i == 0):             return False        return True    # Driver Program  if isPrime(11):     print ("true") else:     print ("false")        # This code is contributed by Sachin Bisht

   C#

   // A school method based C# program to  // check if a number is prime using System;    class GFG {     // function check whether a       // number is prime or not     static bool isPrime(int n)     {         // Corner case         if (n <= 1)             return false;                // Check from 2 to n-1         for (int i = 2; i < n; i++)             if (n % i == 0)                 return false;                return true;     }            // Driver Code     static void Main()      {         if(isPrime(11))              Console.Write(" true") ;                    else             Console.Write(" false");     }  }    // This code is contributed by Sam007

   PHP

   <?php // A school method based PHP program to  // check if a number is prime    // function check whether a number  // is prime or not function isPrime($n) {     // Corner case     if ($n <= 1)         return false;        // Check from 2 to n-1     for ($i = 2; $i < $n; $i++)         if ($n % $i == 0)             return false;        return true; }    // Driver Code if(isPrime(11))     echo("true"); else     echo("false");    // This code is contributed by Ajit. ?>

   
   Output :
   Time complexity :O(n)

   True
   

2. Efficient solutions
   • Primality Test | Set 1 (Introduction and School Method)
   • Primality Test | Set 2 (Fermat Method)
   • Primality Test | Set 3 (Miller–Rabin)
   • Primality Test | Set 4 (Solovay-Strassen)
   • Lucas Primality Test

Algorithms to find all prime number smaller the N.

• Sieve of Eratosthenes
• Sieve of Eratosthenes in 0(n) time complexity
• Segmented Sieve
• Sieve of Sundaram
• Bitwise Sieve
• Recent Articles on Sieve!

More problems related to Prime number

• Find two distinct prime numbers with given product
• Print all prime numbers less than or equal to N
• Recursive program for prime number
• Find two prime numbers with given sum
• Find the highest occurring digit in prime numbers in a range
• Prime Factorization using Sieve O(log n) for multiple queries
• Program to print all prime factors of a given number
• Least prime factor of numbers till n
• Prime factors of LCM of array elements – GeeksforGeeks
• Program for Goldbach’s Conjecture
• Prime numbers and Fibonacci
• Composite Number
• Recent Articles on Prime Numbers!