How to find the greatest prime number that is smaller than $x$? I want to find the greatest prime number that is smaller than $x$, where $ x \in N$. I wonder that is there any formula or algorithm to find a prime ?
 A: As Emilio Novati stated in a comment, the sieve of Eratosthenes will work. The sieve will probably be fast enough for your needs, although potentially faster approaches exist (see Lykos's answer).
I didn't want to bother converting it to pseudocode, so here is a function written in C that returns the greatest prime less than or equal to $N$.
#include <stdlib.h>

unsigned long primeNoGreaterThan(unsigned long N) {
    unsigned long i,j,winner;
    _Bool* primes = (_Bool*) malloc(N*sizeof(_Bool));
    primes[0] = primes[1] = 0;
    for(i = 2; i <= N; ++i) 
        primes[i] = 1;
    for(i = 2; i <= N; ++i) {
        if(primes[i]) {
            winner = i;
            for(j = i+i; j <= N; j += i) 
                primes[j] = 0;
        }
    }
    free(primes);
    return winner;
}

A: There are a few algorithms available. You could for example test for any number smaller than x, starting with x-1 if it is prime, that way if you use the AKS primality test you would probably get the best scaling algorithm for the problem you are describing (polynomial in log(x) ). You could also do simple trial division to assess primality for smaller numbers ($x<10^{10}$).
