Prime number, also known as Prime number, refers to the number that is not divisible by other natural numbers except the number itself (also can be defined as the number that has only two positive factors with the number itself).

How to quickly tell if a number is prime? How do you screen out all the primes in a given interval?

These are the two questions that big factory interviewers often like to examine. In this paper, a variety of ideas are adopted to analyze the above two problems.

All function parameters in this article are natural numbers by default.

The code in this article is in the C++ language, using the following default sources:

# include <cstdio>
# include <ciso646>

namespace Main {
    namespace Source {
        typedef short unsigned int hu;
        typedef unsigned int uint;
        typedef long long unsigned int llu;
    }
    using namespace Source;
    static inline const void main() {}
}

signed int main() { Main::main(); return 0; }
Copy the code

Question 1: Prime number judgment

Determine whether a non-negative integer is prime.

Solution 1.1

By definition, you can write the following code:

static inline const bool isprime(const uint a) {
    if (a == 0 or a == 1) return false;
    for (register uint i(2); i < a; ++i) if (not(a % i)) return false;
    return true;
}
Copy the code

Time complexity, space complexity, problems that can be solved within.

Solution 1.2

Consider optimization.

Let’s see which numbers sieve out a composite number. The following table (denoted as Table 1) may be listed:

Screen out the number 42628293102122142153162182202213222242255262

(The left side is, and the right side is the number of sieve.)

Core code:

static inline const uint mpf(const uint c) {

for (register uint i(2); i < c; ++i) if (not(c % i)) return i;

return 0;

}

We found that all the numbers we screened out were small, and we thought, well, if there are no divisor numbers in a relatively small range, can we call them prime numbers?

Thus, we consider finding the upper limit of the smallest nonfactor of a composite number.

Set as a composite number, let be the least nonfactor of, and let be, obviously.

Is the smallest nonfactor of.

Therefore,.

Therefore, if it is composite, there must be a factor that is not greater than; If there is no factor in, it is prime (except).

So enumeration to can be.

static inline const bool isprime(const llu a) {
    if (a == 0 or a == 1) return false;
    for (register uint i(2); 1ull * i * i <= a; ++i) if (not(a % i)) return false;
    return true;
}
Copy the code

The time complexity, the space complexity, the inner contract can solve the inner problem.

Problem 2: Screening primes in intervals

Sieve out the primes and get a prime number table.

Solution 2.1

You can determine whether each number is prime by looking at the code in 1.2 above.

static inline const bool isprime(const llu a) {... } enum { N = 1u << 20 }; static uint n; static bool isp[N]; static uint prime[N], cp; static inline const void main() { scanf("%u", &n); for (register uint i(0); i < n; ++i) if (isp[i] = isprime(i)) prime[cp++] = i; for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]); }Copy the code

The time complexity, the space complexity, because most of the fraction is composite, the constant is small, the inner approximately can solve the problem.

Solution 2.2

Looking at Table 1, we find that the numbers that sieve out composite numbers are always prime numbers.

So we guess that the smallest nonfactor of a composite number is prime.

Proof: if the smallest factor of which is not, is and is not prime, then there must be some divisors to satisfy; In this case, there must be, and, so, and is the least nonfactor of contradiction. Have to pass.

So we can optimize the isprime function.

enum { N = 1 << 24 };
static uint n;
static bool isp[N];
static uint prime[N], cp;
static inline const bool isprime(const llu a) {
    if (a == 0 or a == 1) return false;
    for (register uint i(0); i < cp and 1ull * prime[i] * prime[i] <= a; ++i)
        if (not(a % prime[i])) return false;
    return true;
}
static inline const void main() {
    scanf("%u", &n);
    for (register uint i(0); i < n; ++i) if (isp[i] = isprime(i)) prime[cp++] = i;
    for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]);
}
Copy the code

The time complexity (by the prime number density in the prime number theorem is approximately), the space complexity, the inner complexity can be solved.

The curves show the number of primes PI (n) (blue), n/ln n (green), and Li(n) (red), respectively.

Solution 2.3

Since primes can be used to determine whether a number is composite, why not just use them to screen out composite numbers? This will save you a lot of unnecessary calculations.

It is easy to think that from the beginning of enumeration, we use ISP [I] to indicate whether it has been screened before. If it is enumerated to a number that has not been screened, it is a prime number, which is used to sieve the composite number behind.

enum { N = (const uint)4e7 };
static uint n;
static bool isp[N];
static uint prime[N], cp;
static inline const void main() {
    scanf("%u", &n);
    for (register uint i(0); i < n; ++i) isp[i] = true; isp[1] = isp[0] = false;
    for (register uint i(0); i < n; ++i) {
        if (isp[i]) {
            prime[cp++] = i;
            for (register uint j(i); j < n; j += i) isp[j] = false;
        }
    }
    for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]);
}
Copy the code

Time complexity, space complexity, problems that can be solved within.

This method is called the Sieve of Eratosthenes, and it’s a very classical sieve of entry.

Intuitive proof of time complexity:

Assuming that prime numbers are uniformly distributed in the interval according to the conclusion of prime number theorem, the sum is transformed into integral, and the number of calculations is about

Solution 2.4

The main disadvantage of 2.3 is that composite numbers are screened out many times, resulting in large time complexity.

Consider allowing each composite number to be screened out by its smallest prime factor.

Let the minimum prime factor of a positive integer greater than or equal to be (obviously if it is a prime number), define.

Consider enumerating prime numbers and positive integers greater than, such that (at this point obviously).

Then, if we can find a way to enumerate all such pairs, we can sieve out all composite numbers (i.e.

Obviously, there is, so it is equivalent to.

Thus, we can enumerate the pairs that satisfy the primes.

Consider enumerations and find that it is not easy to enumerate once determined.

So consider enumerating the positive integers greater than, and then enumerating the primes, such that.

If we decide to enumerate the primes from small to large, then the first prime that satisfies is the one that satisfies all the primes enumerated before.

We can then write the following code:

enum { N = (const uint)2e8 }; static uint n; static bool isp[N]; static uint prime[N], cp; static inline const void main() { scanf("%u", &n); for (register uint i(0); i < n; ++i) isp[i] = true; isp[1] = isp[0] = false; for (register uint i(2); i < n; ++i) { if (isp[i]) prime[cp++] = i; for (register uint j(0); j < cp and 1ull * i * prime[j] < n; ++j) { isp[i * prime[j]] = false; if (not(i % prime[j])) break; I mod prime[j] = 0; I mod prime[j] = 0; } } for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]); }Copy the code

Space – time complexity, about the problem can be solved.

This method is called the Sieve of Euler, and it is a very common sieve method.

This method is often used as a sieving function because it is convenient to distinguish whether there is a multiple relationship between two numbers of composite numbers.

Ok, so that’s the end of our series of interview questions about prime numbers