A prime number is a positive natural number that is greater than 1 and no other divisors other than 1 and itself. For example, 2, 3, 5 are primes but 4, 6, 8 are not. A positive nature number that is not prime is called a composite number.
Finding primes numbers are very common techniques required in number theory-based applications. For example, any positive nature number can be expressed using the multiplication product of the following format:
This is useful to find out the number of divisors for a natural number. For example, 6 can be re-written as . Therefore the total number of divisors for 6 can be calculated as , which are 1, 2, 3, 6. In general, the number of divisors are equal to
In computer science, finding primes can be efficiently constructed using the following two method: checking individual number and Sieve’s method.
To check if any given integer is prime is straightforward. Brute-force implementation is to list the numbers from 2 to itself minus one inclusive, and check if it can be divided by itself, it yes, then it is not a prime, otherwise it is a prime.
This can be improved by only checking a fewer numbers, for instance, only the numbers from 2 to are necessary. To further reduce the checking operations, only check 2, 3 and skip two numbers at a time, to next 5, 7, 9 … The reason for that is simple, if a number can not be divided by two, then it is an odd number, which surely cannot be divided by any even number that is greater than 2.
The following Python code will implement the first idea, which lists the prime numbers from 1 to 70.
#!/usr/bin/env python maxn = 70 def isprime(n): if n <= 1: return False if n == 2: return True if n % 2 == 0: return False for i in xrange(3, int(n ** 0.5) + 1, 2): # skip 1 number at a time if n % i == 0: return False return True p = [] for i in xrange(1, maxn + 1): # check each number and add to the set if it is a prime if isprime(i): p.append(i) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] print p
The Python code n ** 0.5 is the same as sqrt(n),. but simpler, without the need to import the math package.
The second method is based on Sieve’s idea, and it is more efficient if you want to find a prime list rather than just want to know if a number is prime. The idea is to filter out the multiples of the primes in the list and the algorithm can be described as the following steps. [wiki link]
The following Python code illustrates this idea and gives the same prime number set from 1 to 70.
#!/usr/bin/env python maxn = 70 u = [True] * (maxn + 1) for i in xrange(2, maxn + 1): if u[i]: for j in xrange(i * i, maxn + 1, i): u[j] = False #[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] print [x for x in xrange(2, maxn + 1) if u[x]]
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: O(n) High-precision Division Between Two Integers
Next Post: Sleep Sorting in Python, using Threads
another improvement can be done
-1) try divison by 2-3 and 5
-2)switch the step by 2 and 4 alternatively to avoid finding other multiples of 3
exemple
2-3-5 (+2)=7 (+4)=11 (+2)=13 (+4)=17
I give you the code i wrote in C language
/*méthode qui renvoie VRAI si la valeur entrée est un nombre premier
*/
BOOL estPremier (UINT x){
//déclaration des variables
BOOL estPremier = VRAI;//on considère que le nombre est premier jusqu’à ce qu’on démontre le contraire
UINT racine , cpt = 11;
//début du code
racine=sqrt(x)+1;//pour eviter du calcul superflu, on s’arrete a la racine du nombre (eratostene))
if (x>1){
if ((x==2)||(x==3)||(x==5||(x==7))){
return estPremier;
}else{
if((x%2==0)||(x%3==0)||(x%5==0||(x%7==0))){
estPremier=FAUX;
}
}
}else{
estPremier=FAUX;
}
while ((estPremier==VRAI)&& (cpt<=racine)){
if(x%cpt==0){
estPremier=FAUX;
}
cpt=cpt+2;
if(x%cpt==0){
estPremier=FAUX;
}
cpt=cpt+4;
}
return estPremier;
}