Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Check if a number is prime - a bit faster

    Suppose a program that checks primality is currently being used in the production of a large company. Yet, as the company scales rapidly and the number of users increases, so does the number of requests to your code. They ask you to optimize it and make it a bit faster so that the company is able to handle a load of new users coming rapidly.
     
    Your previous solution was most likely
    1. Looping over the numbers from 2 up to n and counting the number of divisors.
    1. Looping over the numbers from 2 up to n and stopping as soon as it found a divisor.
    There are several small tweaks we can do to optimize the procedure:
     
    Optimization 1:
    Instead of looking at all the numbers from 2 to n, we can check if n is divisible by 2 and then check for only the odd numbers. If the number is not divisible by 2, then there is no need to check for all the larger even numbers (4, 6, 8, 10, 12, etc).
    Optimization 2:
    Instead of looping from 2 up to n, we can loop up to n/2 as the smallest possible divisor is 2 ⇒ we won’t be able to find any divisors larger than n/2.
     
    We can combine optimizations 1 and 2. As a result, the candidates will be the odd numbers up to n/2. There are about n/4 such numbers so the code will be 4 times more effective than a plain linear check.
     
    These optimizations will make the code a bit faster but in terms of complexity, the algorithm still performs a linear search for divisors. So, as n increases, the algorithm will do proportionally more operations. We’ll discuss how to drastically optimize the primality checking so that it doesn’t do more work proportional to the increase of n later.

    Input

    The first line of the input contains a single integer n (1 ≤ n ≤ ).

    Output

    The program should print Yes in case n is prime and No otherwise.

    Examples

    Input
    Output
    8
    No
    7
    Yes
    1
    No
    19
    Yes
     

    Constraints

    Time limit: 0.5 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue