Abstract:Interviewer: Do you know how to find a prime number? Me: Primes?

This article is shared from Huawei Cloud Community “The Correct Way to Find Primes that Many People Don’t Know”, the original author is Bigsai.

preface

Interviewers are now a nightmare for many developers, and it’s rare to find someone who can beat an interviewer, because most interviewers are really good at it. But when it comes to interviews, we survivors can’t deny everything. We can only break through on a single point — a question that will surprise the interviewer. This is not, today to share.

This year, the algorithm post volume does not say, the development post is also a little volume, the developer requirements are more and more high, and the interviewer is deliberate “difficult” interview, usually like to start from the shallow to the deep, usually like to ask: do you know why? Do you know how it works? And so on. And, in the past, only big factory interviewers like to ask algorithms, big factory employees have a good foundation, many even have ACM experience or system brush experience, which is easy to understand, but now some small company interviewers are also open mouth, 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 a prime number?

Me: Primes?

Interviewer: Yes, it’s prime.

If a number is prime, then no two numbers (except itself and 1) are equal to it. Just enumerate and see if there are any numbers that can be divisible by it. If there are, then it is not prime.

The interviewer looked disappointed and said I was right, but missed the point. Let me be specific.

Now let’s begin my performance:

First of all, the most stupid way to determine if n is a prime number is to determine if any of the enumerations between [2,n-1] are directly divisible by n. If so, return false. This is not a prime number, otherwise it is a prime number.

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

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

But in fact, this is a waste of time, there is no need to do this, can be optimized. If a number is not prime, it must be the product of two numbers, one larger and the other smaller, and the smaller is less than or equal to the square root of n, and the larger is greater than or equal to the square root of n. We just need to enumerate the smaller possible ranges and see if they are divisible. For example, if 100=250=425=520=1010, you can find the interval between 2 and 10. There must be a corresponding one on the right hand side and you don’t have to worry about it.

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

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

At this point, the interviewer smiled with relief.

Interviewer: Not bad. I’ve got the basics

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

Interviewer: O(n* SQRT (n)) using an array is not bad.

Find many primes

When you have multiple primes (primes less than n), the above method becomes cumbersome, because there’s a lot of double counting, because there’s a lot of double counting when you’re trying to figure out whether a multiple of a number is prime, and if the number is large, you’re wasting a lot of space.

Thus, the concept of a prime sieve was invented and used. The principle of the screen is to carry out a recursive, filter sorting since the prime statistics.

Eratosthenes sieve

If we look at a number that is not prime, then there is no product of numbers that can be prime, then we can operate on this idea:

If the number is prime, then mark the multiple of the number (there is no need to calculate it again next time). If it’s not prime then go to the next step. In this way, the larger the value is, the less the number of calculations will be. When carrying out specific operations, the array can be used to judge. So the core idea of Escherichaft is to determine the multiples of prime numbers as composite numbers.

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 3 and I’m going to label it as a multiple of 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]; // Prime int index=0; // flag prime current subscript 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; }}}

The algorithm complexity of this sieve is O(nloglogn); Don’t underestimate this logn, because if you have a lot of data, a log of a lot less than a zero, that’s ten times, a hundred times, or more.

Euler’s screen

The interviewers are already nodding in agreement and yelling, but that’s not the end of it. There’s also a linear screen — Euler screen. Observe the above Euler sieve, there are many repeated calculations, especially in front of the prime numbers, such as the least common multiple of 2 and 3 is 6, every 3 times the calculation of 2 will also be encountered is a multiple of 3, and Euler sieve on the basis of Euler sieve improvement, effectively avoid this repeated calculation.

What is the idea? Euler sieves, on the other hand, mark a prime number by multiplying it by the known primes, and stop marking backwards if the primes are divisible.

The implementation also uses two arrays, one to store the real and valid prime numbers, and one to be used as tokens.

  • When traversing through a number, if the number is not marked, then the number is in the array of prime numbers, and the subscript is incremented by 1.
  • Whether the number is a prime or not, iterating over a known prime marks its product with that prime. If the prime is divisible by the current value, I, then stop the operation and proceed to the next round.

The code for specific implementation is as follows:

boolean isprime[]; int prime[]; Void getPrimeOoula ()// Euler {prime = new Int [100001]; // Prime 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 ++){// Enumerate isPrime [I * prime[j]] = true; If (I % prime[j] == 0) break; }}}

You might ask why if (I % prime[j] == 0) would break.

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

So if we go to the next round

iprime[j+1]=(prime[j]k)prime[j+1]=prime[j](kPrime [j + 1)) when I = kThe two positions are in conflict with each other, so if you encounter one that can be divisible, stop.

You can see the process, where 6 are labeled 12 instead of 18, and 18 is labeled 9 by 2. You need to look at the code to understand it. I won’t draw the process diagram! Euler’s idea is that what’s closer 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 showed an appreciative expression and said that it was good, and the following was a homely conversation. I was asked to wait for the next interview!

Click on the attention, the first time to understand Huawei cloud fresh technology ~