An overview of the

When I was very young, I knew that there was such a thing as prime number, which could not be decomposed. When I was doing mathematical calculations, I was most afraid of encountering this thing. When I met it, it proved that it could not be divided, and the answer I got was probably not the right answer. But recently, I have done several programming problems related to prime numbers in Project Euler, feeling that I know too little. Today, I will briefly introduce some basic properties of prime numbers, and then combine several programming problems to see.


Basic properties of prime numbers

Wikipedia given above prime Numbers is defined as “except 1 and themselves, cannot be other natural number integer Numbers”, this definition may be long long time to understand you, but I want to ask deep, you probably can’t react immediately, such as problem “how to quickly determine a given number is a prime number?” “And” How are primes distributed among all the numbers, and how can we find them efficiently through algorithms?” If we know that a number is prime, we know that it’s not divisible by a smaller number, and we feel more confident about the program we’re writing, and it’s important to note that all natural numbers greater than 1 can be written as a product of primes, For example, 4 = 2 * 2, 15 = 3 * 5, 20 = 2 * 2 * 5… In other words, as long as we find all the primes in a range, then all the numbers in that range can be found from those primes. Now it seems that primes are the building blocks of natural numbers.

Let’s take a look at some basic properties of prime numbers to help you understand them:

  • All prime numbers are odd except 2
  • All prime numbers greater than 3 can be written as 6k +/- 1
  • Any natural number n greater than 1 can have at most one, except itself, greater than 1Prime factors of

These things aren’t hard, but they’re interesting, so let’s look at them one by one. First of all, this is not hard to understand, except that even numbers are even, and even numbers are divisible by 2, so even numbers greater than 2 have a 2 prime factor, so even numbers are not prime, odd numbers are not prime.

At number two, you might wonder, really? Note that 6k +/ -1 is a necessary condition for a number to be prime, but not a sufficient condition for it to be prime. The number that satisfies this condition is not necessarily prime. And you might ask why that is, but the proof is pretty simple, if you can’t write something as 6k +/- 1, it can be written as 6k +/- 2, 6k +/- 3, 6k +/- 4, and if you look at the past, you’ll see that all three expressions have a prime factor of 2 or 3, So the numbers they represent are definitely not prime.

The last one will help us narrow down the number of prime factors we need to look for. For example, if you want to determine whether 101 is prime, all you need to consider is whether the number divisible exactly from 2 to 10. Why is this true? We know that a number can be written as a product of several or more numbers, like a is equal to b times c is equal to * If b >C must be better thanSmall, otherwise the equation doesn’t work, and then we just have to be at 2Look for the prime factor c, and notice I’m talking about prime numbers here, not 2 ~All of the numbers in. Now, let’s look at some real programming problems to understand how these properties work.


The actual problem

Subject to a

Given a number, find the largest prime factor of the number. For example, the largest prime factor of 100 is 5.

A very direct problem, the most violent solution is to find all the prime numbers in the range of the given number, and then from large to small to see whether these prime numbers are given factors, if so, directly return. This solution space is expensive and time-consuming, and the topic is not for us to find all prime, a better solution is according to nature, any number can be expressed as product of prime Numbers, in the form of a given a number, for example, can be broken down into three prime, b c d e a = b * c * b * c * * d e, So we can eliminate one by one from small to large, no more nonsense, first on the code

public int largestPrime(int n) {
    int largestPrime = 2;

    while (n % 2= =0) {
        n >>= 1;
    }

    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i == 0 && n != i) {
            n /= i;
        }
    }

    if (n > 2) {
        largestPrime = n;
    }

    return largestPrime;
}
Copy the code

You can see that the second for loop starts at 3 and increments by 2 to ensure that it skips even numbers. Of course, for extreme writing, you can consider applying the above properties.All prime numbers can be expressed as 6k +/- 1This property, the other property that’s applied here, is that a number is greater thanThere can be at most one prime factor of, so we only have to worry about divisible less than or equal toIf I have a prime number greater thanIf you have a prime factor of phi, then what you’re left with is phi, and that saves a lot of time. Some people might ask, how can you be sure that everything you divide is prime, and what if it’s not prime? This is easy to explain. As I mentioned before, all numbers can be represented as a product of primes, from small to large, and every time you see a number that is not prime, you can split it into primes smaller than itself, and those primes cancel out a long time ago, so you don’t have to worry too much about them.


Topic 2

Find the 10,000th prime number

There is no way to find primes from beginning to end, because the distribution of primes is irregular (at least not yet), but using some of the properties mentioned above can make the process more efficient. Let’s look at the code below:

private static long findNthPrime(int n) {
    List<Long> primes = new ArrayList<>();

    primes.add(2L);

    long primeCandidate = 3;
    
    boolean isPrime = true;
    while(primes.size() ! = n) {int j = 0;
        isPrime = true;
        while ((primes.size() > j) && (primes.get(j) * primes.get(j) <= primeCandidate)) {
            if (primeCandidate % primes.get(j) == 0) {
                isPrime = false;
                break;
            }
            ++j;
        }

        if (isPrime) {
            primes.add(primeCandidate);
        }

        primeCandidate += 2L;
    }

    return primes.get(primes.size() - 1);
}
Copy the code

So here I started by creating a list of the primes that I found. Why want to find all prime Numbers before, in fact this is not necessary, but all the number can be written as the product of prime Numbers, if you are currently number no one prime factor, it shows the current number is prime, note that here we only need to be considered a prime factor, so need to use the list record prime, or have to go back and look at, It’s a waste of time to think twice about the number you found before, so it’s important to keep track of it. In addition, the second while loop applies the previous properties to narrow the scope of consideration.


The title three

Find the sum of all prime numbers up to 2 million

解 析: There is no special place in this question and the above question, or find, directly on the code:

private static long sumOfPrimes(int upperLimit) {
    long result = 0;

    List<Integer> primes = new ArrayList<>();

    result += 2L;
    primes.add(2);
    boolean isPrime = true;
    for (int i = 3; i < upperLimit; i += 2) {
        int j = 0;
        isPrime = true;
        
        while (primes.size() > j && primes.get(j) * primes.get(j) <= i) {
            if (i % primes.get(j) == 0) {
                isPrime = false;
                break;
            }

            ++j;
        }

        if (isPrime) {
            primes.add(i);
            result += (long)i; }}return result;
}
Copy the code


conclusion

The above is all the content of this share, is not to have a deeper understanding of prime numbers, feel that some seemingly simple, common mathematical properties can indeed bring a qualitative leap for the efficiency of program operation. Here again, I recommend Project Euler, a website for solving problems. For how doing problems on this website can help me improve my ability, please refer to an article in the ARTS Review section of this issue

Consider Yourself a Developer? You Should Solve the Project Euler Problems

Seemingly Project Euler websites can still add buddy, if interested in brush this logic mathematics topic friend can add my friends, my key is 1525929 _nehosvnpcmhyu9ei1hoekljz1xlnoaea, we discuss together, sharing, playing chicken blood.