[python] py class computer assignment 1 "large prime number" and "definite integral"

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.

Idea:
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

Code area:

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).

Idea:
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

Code area:

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)

Idea:
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

Code area:

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;

Tags: Python Algorithm

Posted by chaffinator on Mon, 02 May 2022 03:33:31 +0300