Recently, I have read a lot of problems on the number of prime online. I have learned a lot of things, I decided to organize it, and it is a summary of learning.
The first thing to explain is that although the number can be studied in depth (such as the application of the RSA public key system), but because I am not familiar with the number theory, I can only do some discussion, mainly for some simple A number of related algorithms for a discussion.
First, let's talk about the number of prime numbers. If you are a "C program design" of Tan Haoqiang, then talk about the number of judgment algorithms, you should first think that the following algorithm is given: given a positive integer n, Remove N with 2 to SQRT (N), if it can be divided, then n is not a prime number, if it is not an entire, then n is the number of prime. The time complexity of this algorithm is very clear, it is O (SQRT (n)), the description of the algorithm is quite simple, and it is also not difficult.
# include
INT ISPRIME (INT N) {INT I; For (i = 2; i <= SQRT (N); i ) {IF (N% i == 0) Break;}
IF (i <= sqrt (n)) Printf ("% D is not a prime!", & n); Else Printf ("% D is a prime!", & n); return 0;}
