The realization of prime number decision algorithm

1.   Prime number determination problem

The prime number decision is a very common problem. This paper introduces several common decision methods.

2.   The original algorithm

A prime number is defined as something that is not divisible by anything except 1 and itself. By prime definition, you just divide n by 2 to n minus 1, and if you can't divide them all, then n is prime, otherwise, if one of them is divisible, then n is not prime.

bool is_primer1(int num) {

 

  int i;

 

  for(i = 2; i < num; i++) {

 

    if(num % i == 0) {

 

      return true;

 

    }

 

  }

 

  return false;

 

}

3.   Improved algorithm

N is not a prime number, then n can be expressed as a*b, where 2 < = a < = b < Is equal to n minus 1, then there must be a number in a and b that satisfies: 1 < x < = SQRT (n), therefore, only 2~ SQRT (n) to remove n, so as to get an algorithm with O(SQRT (n)) complexity

bool is_primer2(int num) {

 

  int i;

 

  int upper = sqrt(num);

 

  printf("primer2:%dn", upper);

 

  for(i = 2; i <= upper; i++) {

 

    if(num % i == 0) {

 

      return true;

 

    }

 

  }

 

  return false;

 

}

4.   Filtering algorithm

A more efficient method for judging primes should be to save primes in a primes table in advance. When determining whether a number is a prime number, directly look up the table. This approach requires solving two problems:

(1)   How to get a prime table quickly? (screening method)
(2)   How to reduce the size of a prime table? (bitmap data structure)

All of the integers from 1 to n, one by one, determine if they are prime Numbers, find a non-prime number, dig it out, and you're left with a prime number. The specific method is:

< 1 > Define is_primer[I] = true;
< 2 > Starting at 2, the entire is_primer(up to SQRT (N)) is iterated, and if is_primer[I]=true, is_primer[N * I]=false
If 1,2,3,4,5,6,7,8,9,10,
Traverse from 2:
Is_primer [2]=true, then is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true
Is_primer [3]=true, then is_primer[6]= is_primer[9]= true
In order to reduce the memory utilization, the algorithm USES bitmap data structure.

bool load_primer_table1() { //Save the prime table 

 

  int i;

 

  for(i = 1; i < INT_MAX; i++) {

 

    if(i % 2 != 0 //Even Numbers must not be prime 

 

      && is_primer2(i)) {

 

      set(i);

 

    }

 

  }

 

}

 

bool load_primer_table2() {// Another faster way Save the prime table 

 

  int i, j;

 

  for(i = 1; i <= INT_MAX; i++) {

 

    if( i % 2) {

 

      set(i);

 

    } else {

 

      clear(i);

 

    }

 

  }

 

  int upper = sqrt(INT_MAX);

 

  for(i = 1; i <= upper; i++) {

 

    if(test(i)) {

 

      for(j = i + i; j < INT_MAX; j += i)

 

        set(i);

 

    }

 

  }

 

}

 

bool is_primer3(long num) { //Look up the table to see if it is prime 

 

  if(test(num))

 

    return true;

 

  return false;

 

}

5.   Optimized screening algorithm

(1)   Storage mode optimization

Bitmap storage is still used, but only odd Numbers are stored in the bitmap, which suddenly saves half of the space (only 4G/(32*2)=64MB).
After the storage space optimization, the efficiency of the algorithm will be improved a lot, such as: 1,2,... , 30
Store only 3,5,7,9,11,13,15,17,19,21,23,25,27,29
I = 0, is_primer [0] = true, the subscript [3] [6] [9] [12], namely 9,15,21,27, marked as false
I =1, s_primer[0] =true, index [6][11], i.e., 15,25 false
I = 2, 2 * I + 3 > SQRT (30), the end
I =s, subscript as s(2*t+1)+3t, where t=1,2,3... All the is_primer sets to false

(2)   Optimize the selection algorithm

A is a prime number, so the next starting point is a times a, and I'm going to sieve out all the a times a plus 2 times I times a. That is, to find the prime number within n, we first calculate the prime number in SQRT (n), and then screen out the composite number behind with the prime number already obtained.

6.   conclusion

So far, no one has discovered the distribution of primes, and no one can calculate all primes in one formula. Many interesting properties of prime Numbers or the efforts of scientists, such as:

(1)   Gauss's guess is that the number of primes up to n is about the same as n over the natural log of n, or the same order of magnitude when n is large. This is the famous prime number theorem.

(2)   Fermat guessed in the seventeenth century that 2 to the 2 to the n plus 1, n = 0,1,2... This is called a fermat prime, but when n=5, 2^32+1 is not a prime, and we haven't found the sixth fermat prime yet.

(3)   The largest prime number discovered in the 18th century was 2^31-1. The largest prime number discovered in the 19th century was 2^127-1. The largest prime number known to man at the end of the 20th century was 2^859433-1.

(4)   Twin prime conjecture: there are an infinite number of pairs of prime Numbers with a difference of 2. The largest known prime twin Numbers are 1159142985 times 2^2304-1 and 1159142985 times 2^2304+1.

(5)   Goldbach's conjecture: all even Numbers greater than 2 are the sum of two primes, and all odd Numbers greater than 5 are the sum of three primes. The second conjecture is a natural consequence of the first, so the gedbach conjecture is also known as the 1 + 1 problem. Chinese mathematician Chen jingrun proved that 1 + 2, that all even Numbers greater than 2 are the sum of a prime number and composite Numbers with only two prime factors. Internationally known as Chen's theorem.