Find square root of a number without using square root

Give a number find square root of number without using square root function.

Solution:
So given x we need to find sqrroot(x) = y
i.e. x = y^2

so we need to a find a y whose square is x.

We can use binary search to find such a y

Fo eg we need to find sqrroot(100)
We can start doing binary search between 0 and 100. First iteration we find 50 and 50^2 > 200 so we move left partition and visit 0 and 50 and keep continuing till we find our number

Finding prime numbers

Source

Output all prime numbers up to a specified integer n.

This is a phone screen question from one of my interviews. An efficient way to generate prime numbers is usingSieve of Eratosthenes. We store the primes in a table of true false values, so we are able to determine if a number is a prime number efficiently using this table.

Below is one possible implementation, you can read more in-depth analysis about generating prime numbers inProgramming Pearls.

/* Generate a prime list from 0 up to n, using The Sieve of Erantosthenes param n The upper bound of the prime list (including n) param prime[] An array of truth value whether a number is prime */ void prime_sieve(int n, bool prime[]) {   prime[0] = false;   prime[1] = false;   int i;   for (i = 2; i <= n; i++)     prime[i] = true;     int limit = sqrt(n);   for (i = 2; i <= limit; i++) {     if (prime[i]) {       for (int j = i * i; j <= n; j += i)         prime[j] = false;     }   } }