Perhaps one of the problems that all programmers are encountered when programming is the problem of checking whether an integer is a prime or not.

The first algorithm to us that: check the number is likely to be a divisor of n (Some need to check the elements), the number ranges from 2 to n – 1. The algorithm is installed by following simple C:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i < n; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

During installation on, if n is prime, the loop will run until i = n – 1 to be able to make final. However, Think a little more we will see that do not need to check the value of i = n – 1 which is actually just to n / 2 (a div 2) because no divisors of n greater than n / 2. So the algorithm is as follows:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= n / 2; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

Back to think a bit more we will see that is not necessary to check the value of n / 2, but just to root 2 of n is (you calculate a bit to see why so ). I have a new algorithm: (Note declare library math.h to frugality)

#include <math.h>

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return 0;
	return 1;
}

The number of elements can only be the odd exception of 2, and therefore we can not divisible by even numbers, so we just need to check the divisor (the value of i) is odd, so the next algorithm is as follows:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;
	if (n < 2)
		return 0;
	if (n == 2)
		return 1;
	if (n % 2 == 0)
		return 0;

	m = (int) sqrt(n);
	for (i = 3; i <= m; i += 2)
		if (n % i == 0)
			return 0;
	return 1;
}

Obviously, compared to the previous algorithm, of the value of i should check halved. Thus the key to accelerate and improve the algorithm lies in the statement changes the value of the control variable i, I just dropped some value of i should check that will lead to a more efficient algorithm.
Recently we have removed half of the value of i by considering divisor 2 can have n. Next we improve the algorithm by considering the next prime divisors of n may be some 3. If n is divisible 2 or 3 it is easy to conclude that the number of (n of course have two different values). Conversely n will be a divisor of the form 1 6i,5+6in , I will start with the value i = 5. But if only i will be missing test candidates in the form of 1 6i, so we will check value i 2 (noted: when we start with i = 5, we have i 2 <= & Gt; 1 6i) enough. So the new algorithm (5) will be as follows:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;

	if (n < 2)
		return 0;

	if (n == 2 || n == 3)
		return 1;
	if (n % 2 == 0 || n % 3 == 0)
		return 0;
	
	m = (int) sqrt(n);
	for (i = 5; i <= m; i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return 0;
	return 1;
}

In the problem that the number of elements to be checked repeatedly we can improve the algorithm by using technology sieve elements here.

Through the presentation of a simple algorithm to check the small primes, I hope that gives you a good algorithm to be used in the programming contest problems or within small, and thereby illustrate the settings to tweak an algorithm. Maybe the same algorithm but with different settings, effectiveness will vary, and more effective when it is based on the details seemed very small, not remarkable.

If there is any good algorithm, there are, we're looking at achievements to our shared discussion, learn more.

Original article / Source: vietsource.net