Interviewer: Do you know how to find prime numbers? Me: Prime?

This article is shared from huawei cloud community “many people do not know the correct way to find prime numbers”, the original author: Bigsai.

preface

Today’s interviewers are the nightmares of countless developers, and there’s not much truth to be said for them, because most interviewers are really good at that. But in interviews, we survivors can’t just say no — we can only do something to impress the interviewer. This, today to share.

This year, the algorithm does not say inside the volume, the development of the post is also a little inside the volume, the developer requirements are getting higher and higher, and the interviewer is also a thoughtful “difficult” interview, all like from shallow to deep, all like to ask a: you know why? Do you know how it works? And so on. And, in the past, only big factory interviewers like to ask algorithm, big factory employees have a good foundation, many even have ACM experience or system brush experience, this is easy to understand, but now some small company interviewers are also mouthing xx algorithm, XX data structure you say, this is not really asked.

Find a prime number

In such a process, the interviewer ask me algorithm problem I’m not surprised, before I put ten sort principle, complexity analysis, code written out, also the linked lists, trees, a variety of operating review thoroughly, but suddenly is surprised the interviewer to a prime number problem, I restore a scenario:

Interviewer: Do you know how to find prime numbers?

Me: Prime?

Interviewer: Yes, prime numbers.

I: This is very simple ah, to determine that a number is prime, then there must be no two numbers (except itself and 1) equal to it, just enumerate to see if there is a number that is divisible by it, if there is then then is not prime, if not, then is prime.

The interviewer gave me a disappointed look and said I was right but not to the point and asked me to elaborate.

Let’s begin my performance:

First, the dumbest way to check whether n is prime is to check whether there are any enumerations between [2,n-1] that are directly divisible by n. If there are any, return false that is not prime, otherwise it is prime.

boolean isprime(int value){ for(int i=2; i<value; i++) { if(value%i==0) {return false; } } return true; }Copy the code

The time complexity of a prime number is O(n).

But it’s a waste of time, it’s not necessary, you can optimize it. If a number is not prime, then it must be the product of two numbers, and these two numbers are usually a large number and a small number, and the small number is less than or equal to the square root of n, and the large number is greater than or equal to the square root of n. We just need to enumerate the small range of possible, see if it can be divisible, then we can determine whether the number is prime. For example,

50 = 100 = 2 * 4 * 25 = 5 * 20 = 10 * 10

You just have to look for the interval between 2 and 10. There’s got to be a corresponding one on the right hand side and I don’t care about that.

boolean isprime(int value) { for(int i=2; i*i<value+1; i++) { if(value%i==0) {return false; } } return true; }Copy the code

And the reason why it’s less than value plus 1 is because it includes the square root, so 3 times 3 is 9. To include 3. This time complexity of the single number is O(SQRT (n)). Interviewer: Let me draw you a picture to show you the difference:

Here the interviewer smiled with relief.

Interviewer: Good, good. I’ve got the basics

Me: elder brother, in fact, the essence of finding prime numbers is not here, this is too inefficient in many cases, such as finding all prime numbers less than n, you see how to do?

Interviewer: O(n* SQRT (n)) is ok with the second method using an array.

Find multiple prime numbers

The above method is very tedious when we are dealing with multiple primes (primes less than n), because there is a lot of double calculation, because there is a lot of double calculation when we are calculating whether a multiple of a number is a prime number. If the number is large, there is a lot of waste of space.

Thus, the concept of prime sieve was invented and used. The principle of the sieve is a kind of recursion, filtering sorting from front to back to count prime numbers.

Eratosthenes sieve

If we look at a number that is not prime, then no product of the numbers can be used for it, then we can operate with this idea:

Enumerating directly from the front to the back, the position of this number is not marked must be prime, if this number is prime then mark the multiple of this number (the next traversal does not need to calculate). If it’s not prime then go to the next step. In this way, the larger the value is, the less times the calculation is. In the specific operation, the array can be used to judge. So the core idea of an Escherichia is to make multiples of prime numbers composite.

If we start with all prime numbers, and 2 is prime, then no multiple of 2 is prime; And then I’m going to go to multiples of 3 and 3; The next one is 5(because 4 has already been marked); All the way to n minus 1. The specific process can be seen in the picture:

The specific code is:

boolean isprime[]; long prime[]; void getprime() { prime=new long[100001]; Int index=0; Isprime =new Boolean [1000001]; For (int I =2; i<1000001; i++) { if(! isprime[i]) { prime[index++]=i; } for(int j=i+i; j<1000000; J =j+ I) over {isprime[j]=true; }}}Copy the code

The complexity of this screening algorithm is O(Nloglogn). Don’t underestimate this logn, because if you have a lot of data, you can lose a lot of zeros in a log, and you can lose ten times or a hundred times more in time.

Euler’s screen

The interviewer is already nodding his head in agreement, oohing and aahing, but that’s not the end of it. There is also a linear sieve – euler sieve. Observe the above Sieve, there are a lot of repeated calculation, especially in front of the prime number, such as the least common multiple of 2 and 3 is 6, every 3 times 2 calculation will also encounter is a multiple of 3, and euler sieve improved on the basis of the Sieve, effectively avoid the repeated calculation.

What is the specific idea? That is, an Escher’s sieve is one that comes across a prime number and counts its multiples to the end, whereas an Euler sieve is simply marked by multiplying it by the product of known primes, and stopping marking if the primes are divisible.

The implementation also uses two arrays, one for real and valid prime numbers and one for token use.

  • When we iterate over a number, if the number is not marked, then the number is in an array of prime numbers and the subscript is incremented by 1.
  • Regardless of whether the number is prime or not, iterate over a known prime number and mark it with the product of that prime number. If the prime number is divisible by the current value I, stop the operation and proceed to the next round.

The specific implementation code is:

boolean isprime[]; int prime[]; Void getPrimeOula () {prime = new int[100001]; Int index = 0; isprime = new boolean[1000001]; for (int i = 2; i < 1000001; i++) { if (! isprime[i]) { prime[index++] = i; } for (int j = 0; j < index && i * prime[j] <= 100000; J ++){isprime[I * prime[j]] = true; If (I % prime[j] == 0) break; }}}Copy the code

If (I % prime[j] == 0) break

If I %prime[j]==0, then I =prime[j]*k. k is an integer.

I *prime[j]=(prime[j]*k)*prime[j+1]=prime[j]*(k*prime[j+1]) When I =k*prime[j+1], there is a conflict between the two positions.

You can see the process, 6 is labeled 12 but not 18,18 is labeled by 9 times 2. A detailed understanding requires a bit more thinking about the code. I won’t draw the process diagram! Euler’s idea is that the one closest to me I’ll label it. The time complexity of the Euler sieve is O(n) because each number is marked only once.

The interviewer had an appreciative look on his face and said, Well done, here’s a little bit of homeland to keep me waiting for my next interview!

Click to follow, the first time to learn about Huawei cloud fresh technology ~