Tutorialspoint.dev

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

Algorithms to find all prime number smaller the N.

More problems related to Prime number



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter