What is Prime Number?
Prime numbers are whole numbers greater than 1 that have only two factors. 1 and the number itself. Prime numbers are divisible only by the number 1 and itself.
1 itself is not a prime number.
The first prime number is 2. Two is the only even prime number. Because the rest of the even numbers are divisible by 2.
3, 5, 7 are some of the prime numbers. Because only 1 and the number itself can divide them.
But 4 or 6 are not prime numbers. 2 can divide 4 and 6 can be divided by 2 and 3.

How many prime numbers are there?
There are infinite number of prime numbers. Mathematician Euclid proved that prime numbers can not be finite.
Suppose, someone claimed that there are P_n prime numbers.
Let's multiply those P_n primes and add 1 with the answer. Let's the number be X.

X = P₁ * P₂ * P₃ * .......... * P_n-1 * P_n + 1.

X-1 will be divisible by those primes. But X can not be divided by any of the P_n prime numbers. Every time there will be a remainder equal to 1. So, X is a prime number. We can say that no one can claim that prime numbers are finite.
But will the multiplied value always be a prime number?
Let's multiply every prime number till 13.

2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031

But 30031 = 59 * 509. That's not a prime number.
We proved that prime numbers are not finite. The prove does not says the new value will be a prime number.

What is Co-Prime?
A set of integers with two or more value can be called coprime if its elements share no common positive factor except 1.
Let's look at the numbers 21 and 22.
Divisors of 21 are 1, 3, 7, 21. Divisors of 22 are 1, 2, 11, 22.
They don't have any common divisor other than 1. So they are Co-Prime.
But 21 and 27 are not co-prime. Divisors of 21 are 1, 3, 7, 21. Divisors of 27 are 1, 3, 9, 27. There are another common divisor other than 1 between 21 and 27. That is 3. so they are not co-prime.

Some properties of Co-Prime:

1 is Co-Prime with every number.

All prime numbers are Co-Prime to each other. Because no prime number has any divisor other than 1 and itself.

Two adjacent numbers are always Co-Prime. Because the divisors of the first number can not divide the second number. There will be always a remainder equal to 1.

The sum of any two co-prime is always co-prime with their product. Summation of 5 and 6 equals to 11 and the product is 30. Here, 30 and 11 are Co-Prime to each other.

How can we check that if a number is prime or not?

Prime numbers can not be divided by any numbers other than 1 and itself. So, for a number n, we can simply check if the number is divisible by any number from 2 to n-1.

 
bool IsPrime( int n )
{
    for ( int i = 2 ; i < n; i++ )
    {
        if ( n % i == 0 )return false;
    }
    return true;
}

Can we make the process faster?
No even numbers are prime number except 2. So, first we can check if the number is even. Then we can skip checking for even numbers inside the loop.
Can we divide n with any value greater than n/2?
We don't need to run the loop till n-1. We can check only the first half numbers of n.
Can we make the process even faster?
Yes, we can!
Let's find out the divisors of 64.
The divisors of 64 are 1,2,4,8,16,32,64.
Let's align them pairwise.
1 * 64 = 64
2 * 32 = 64
4 * 16 = 64
8 * 8 = 64
We can easily see that the smaller numbers are always less than or equal to the Square Root of 64.
So, for checking the divisors of 64, we can check each number till the Square Root of 64. To check if a number is prime or not we can loop over the numbers less than or equal to the square root of this number and check if the number can be divisible. Let's check for the number 64. Square root of 64 is equal to 8. Here, 8 * 8 equals to 64. If we increase one of these numbers it will become 8 * 9 = 72. We can see that the answer is greater than 64.
Try to write the code yourself first.

bool IsPrime( int n )
{
    ///Checking if the number is 2 or an even number
    if ( n == 2 )return true; 
    else if ( n % 2 == 0 )return false;

    ///Checking if the number is divisible by the odd number under square root
    for ( int i = 3 ; i * i <= n; i++ )
    {
        if ( n % i == 0 )return false;
    }
    return true;
}

Hope that you understood clearly. Solve the problems given below!

Practice Problems:
10235 - Simply Emirp (Uva) Online Judge.
10924 - Prime Words (Uva) Online Judge.
Noldbach problem - Codeforces.