This is a problem from an ACM practice session at a school, which is quite frustrating.
The reason why I want to talk about prime number algorithms today is completely related to this problem. Friends who have seen the problem must already have some ideas, but the explanation below may make you feel frustrated. Hoho, bring your thinking and follow me.
First, analyze the problem. Excluding within 10000, we need to find a prime number that satisfies the condition that its value is equal to the sum of the squares of two prime numbers.
K = A^2 + B^2. Here, A and B are prime numbers, and K is the desired prime number. So, a good solution would be to find one prime number, and then find another different one. Why different? If K is greater than 2, then K is definitely not a prime number. Then, square them and add them together. Finally, verify if the obtained K is a prime number. To be honest, when you wait for N seconds and still don't get the result, you will feel that your algorithm needs optimization. Actually, that's what I thought at the beginning, but the result...
Okay, let me talk about my idea and some mathematics.
(1) (A + B)^2 = A^2 + 2*AB + B^2. This is the conversion formula between "sum of squares" and "square of the sum".
(2) Parity formula: The sum of two even numbers is even, the product of two even numbers is even. The sum of two odd numbers is even, the product of two odd numbers is odd. The sum of an odd number and an even number is odd, and the product is even.
(3) Goldbach's conjecture: The sum of any two prime numbers greater than 2 is even.
The third point is very important. Although it is a conjecture, it can be proven for data sizes that can be calculated in computer science, such as by exhaustive method.
After talking about mathematics, let's continue with our algorithm optimization. Please continue reading the analysis below.
K = A^2 + B^2 => K = (A + B)^2 - 2*AB
Since A + B is even (according to Goldbach's conjecture), (A + B)^2 is also even. If K is a prime number and K is not equal to 2, then K is definitely odd. Why? I won't explain this. Let's continue the deduction.
K is odd, (A + B)^2 is even, so 2*AB must be even. When you multiply a number by 2, it becomes even. The sum of two even numbers is even. But K is a prime number, not even. Why? So, it can be concluded that one of A and B must satisfy a special condition, such as being 1 or 2.
So, if A = B = 1, K = 2, which meets the requirement. If one of A and B is 1, for example, A = 1, B = 3, K = 10, which does not meet the requirement. Moreover, the square of an odd number is odd, so adding 1 to this odd number will definitely make it even. Why bother with even numbers? If A = B = 2, K = 8, which does not meet the requirement. Therefore, A and B must satisfy a certain condition: one of them must be 2, and the other must be another prime number. Let's consider the case of 1 and 2 separately: K = 5, which meets the condition.
In conclusion, the set of K {2, 5} plus other cases where one number is 2 and the other is a prime number other than 1 and 2.
So, the algorithm can be optimized to:
K = 4 + B^2. This is much simpler, right?
The algorithm is as follows (in pseudocode): The algorithm complexity is O(N), but it can be optimized to O(SQRT(N)) by adding the complexity of the prime number judgment. The worst-case scenario is still O(N^2).
Compared to the method of first finding two prime numbers, then squaring them, and then checking if it is a prime number, this method indeed reduces a lot of consumption.
//isPrime() checks if a number is prime
int N = 10000
int i;
for i = 3 to sqrt(N)
if isPrime( i^2 + 4)
return(i^2 + 4)
else
i = i + 1