1. Large prime
In encryption related algorithms, it is often necessary to quickly generate some large prime numbers. Please write a program to generate a prime number as large as possible within a given time (such as 3 seconds) and give its digits at the same time.
To tell you the truth, I was a little confused when I saw this topic at the beginning. Generate a prime number as large as possible. How big is the largest? Different from c + +, there is a data type constraint. In python, I can't imagine what the boundary of number is The only clue is the limited 3s
It suddenly occurred to me that I can try to generate a number as large as possible, and then judge whether it is a prime number. If it is not, add it near it and look for it again and again. There will be prime numbers!
Then the new problem comes again. How to generate a number as large as possible? Considering that the time is limited, I thought of using bit operation to quickly get a large number. However, because we don't understand the concept of 3s for our computer, we shift it to the left from 1, and moving one bit is equivalent to multiplying 2 Then judge the generated number as a prime number. If it is a prime number, record it. At the same time, increase the number of moving digits to obtain a larger number of digits. If the generated number is not a prime number, try adding one and judge again. It will always be added to the prime number (laughter ~) In order to make the increase of the number of moving digits more random, I add a number from 1 to 100 to him every time, thinking: adding the number of moving digits all the time will always produce a large number, which is in line with our purpose
But the problem is how to judge prime numbers When it comes to this problem, we may have some classic methods in mind, such as dividing through the for loop. As long as it is not divided, it is prime Unfortunately, this doesn't seem to work in this problem Because the time efficiency is too low, it's too slow to find it again and again What can I do? (of course, I choose to ask Du Niang) good guy, after checking, I found that there is an algorithm for judging prime numbers, which is called Miller Robin, that is, an algorithm for verifying prime numbers developed by Miller Rabin. Although I don't know much about specific mathematical logic (I'm not a math student after all, right), I can use it directly It seems that the prime number is established after passing the Miller robin algorithm for a certain number of times (probably not)
Then the problem of judging prime numbers is solved, and the remaining problem is only time. How to limit time? I restrict it in this way: at the beginning, first record the start time of the program as start using the time method in the time third-party library, and then judge when the program judges the prime number. Once it is found that the current time (also obtained through the time method) minus start is greater than or equal to 3s, stop the program, and output the maximum prime number and its digits recorded before
import random import time def miller_rabin(p): if p == 1: return False if p == 2: return True if p % 2 == 0: return False m, k, = p - 1, 0 while m % 2 == 0: m, k = m // 2, k + 1 a = random.randint(2, p - 1) x = pow(a, m, p) if x == 1 or x == p - 1: return True while k > 1: x = pow(x, 2, p) if x == 1: return False if x == p - 1: return True k = k - 1 return False def is_prime(p, r=5): for _ in range(r): if not miller_rabin(p): return False return True def main(): num_max = 0 c = 1 end = 0 start = time.time() # Record the current time and save it as start while True: num = 1 << c # Get as many as possible while not is_prime(num): num = num + 1 # +1 continue to judge prime numbers if time.time() - start >= 3:# When the time is up, end the program print('--------Elapsed time:', end - start, 's----------') return num_max c += random.randint(1, 100) num_max = max(num_max, num) end = time.time() number = main() print('--------The number of digits is:', len(str(number)), '----------------------------') print('Prime number is:', number)
2. Mason prime
Mason prime numbers are derived from Mason numbers.
The so-called Mason number refers to a class of numbers in the form of 2p-1, in which the index p is a prime number and is often recorded as Mp. If a mason number is a prime number, it is called a mason prime number.
It can be proved by factorization that if 2n-1 is a prime number, then the index n is also a prime number; On the contrary, when n is prime, 2**n-1 (i.e. Mp) may not be prime. The first few smaller Mason numbers are mostly prime numbers. However, the larger the Mason number, the more difficult it is to appear.
Since Mason put forward his assertion, almost all the known maximum prime numbers are Mason prime numbers. Therefore, the process of finding a new Mason prime number is almost the same as that of finding a new maximum prime number.
The exploration of Mason prime is very difficult. It requires not only profound theory and skilled skills, but also hard calculation.
Please write a program to generate as many Mason primes as possible in a given time (such as 3 seconds).
This problem can be said to be the brothers and sisters of the previous problem. In fact, after the previous problem is done, this problem can be said to be done It's also about prime numbers, but the last question is to output a prime number as large as possible in 3s, while this question is to output as many Mason prime numbers as possible
We can deal with the so-called Mason prime number in this way. We can find the prime number from 2, add one every time, and then judge the prime number. The prime number that meets the condition of Mason prime number will output it, and the counter will add one at the same time Finally, stop running the program at the end of time
The other parts are consistent with the previous question
import random import time def miller_rabin(p): if p == 1: return False if p == 2: return True if p % 2 == 0: return False m, k, = p - 1, 0 while m % 2 == 0: m, k = m // 2, k + 1 a = random.randint(2, p - 1) x = pow(a, m, p) if x == 1 or x == p - 1: return True while k > 1: x = pow(x, 2, p) if x == 1: return False if x == p - 1: return True k = k - 1 return False def is_prime(p, r=5): for _ in range(r): if not miller_rabin(p): return False return True def main(): end = 0 start = time.time() num = 1 count = 0 while True: num += 1 while not is_prime(num): num = num + 1 p = 2 ** num - 1 if is_prime(p): if time.time() - start >= 3: print('--------Elapsed time:', end - start, 's----------') return count print(p) count += 1 end = time.time() cnt = main() print('eureka', cnt, 'Mason prime')
3. Definite integral
Combined with the definition of definite integral, write a function integral to calculate the definite integral of integrable function f on interval [a,b]. After testing this function, for example, use this function to calculate the unit circle area. (for practice: List derivation, parameter default value, lambda function and other syntax or usage)
To calculate the definite integral, we need to introduce sympy, a third-party library Because we need to use the variable x, we need to introduce the variable x first
Since the area of the circle is required, the corresponding integrand function is sqrt(r^2 - x ^2) After this is clear, you can use the integrate method in symphony. The parameters of this method are a function and the upper and lower limits of two integrals
Let's first find a quarter of the area of the circle, so that the lower limit of the integral is 0 and the upper limit of the integral is the radius Finally, multiply by 4 The detailed code is shown below
import sympy from sympy.abc import x def integral(function, b, a=0): return sympy.integrate(function, (x, a, b)) if __name__ == '__main__': r = int(input('Please enter a radius:')) fx = sympy.sqrt(r ** 2 - x ** 2) circle = lambda fa, ra: 4 * integral(fa, ra) print('Circle area is:', circle(fx, r))
Novice on the road, please correct if you make a mistake;