Title 1525: Blue Bridge Cup algorithm to improve VIP prime

time limit: 1Sec Memory limit: 128MB Submit: 2503 solve: 347
 Title Description
 Given interval[L,  R]  ，  Please calculate the number of primes in the interval. 


input
 Two numbers L and R.  



Data scale and agreement
2  < =  L  < =  R  < =  2147483647  
R-L  < =  1000000

output
 A row, the number of primes in the interval.
sample input 
2 11
 sample output 
5

analysis

• Whether this problem is a simple trial division method or a simple Elsevier sieve, the former is easy to time out, and the latter is easy to explode space!!!
• Therefore, there are certain skills in opening up space and writing status here. For example, let's not open a space b and look at the scope of b. It's easy to explode space!!
• Remember, as we said earlier, the emerald sieve is suitable for the data volume of the 7th power of 10, but R-L is the 6th power of 10, which is just less than this range, so the emerald sieve can be used. For example, if my interval is [1000020000], I open up 10001 spaces (10001 spaces for 10000 to 20000). If 10000 corresponds to space 010001 corresponds to space 110002 corresponds to space 2. Did you find the law? The corresponding space of n is n-10000 (i.e. n-a)
• First of all, we should know whether the interval [a,b] is a prime number. Using the trial division method, we only need to round up the root sign B. This is the scope of the Egyptian sieve. The previous method is the same as that of the Elsevier sieve. Multiply by the corresponding multiple, and the status of the marked non prime number is false.
• We need to know the starting point of our sieve data (2,3,5...) and sieve interval data [a,b]. After a little thought, it is not difficult to find out that the starting point is math Ceil (A / I) * I, you can give a little example, or induction.
• Screen interval data here is the place where i didn't get full marks at the beginning (pit!!!): Since interval data and sieve data may be repeated, those repeated with i must be set as True (because the premise is that i is a prime number)

code

import math

a,b = map(int,input().split())
m = int((math.sqrt(b)+1))
flag = [True]* (m+1)
nums = [True]*(b-a+1)
flag[1] = False

# Make the sieve
for i in range(2,m):
    if flag[i]: # Is a prime number
        for z in range(i*i,m+1,i):
            flag[z] = False
        for j in range(math.ceil(a/i)*i,b+1,i):
            if j == i:
                nums[i-a] = True
            else:
                nums[j-a] = False


res = 0 # Number of record primes
for i in nums:
    if i:
        res+=1
print(res)

Through screenshot

Topic 1464: Blue Bridge Cup basic exercise VIP decomposition quality factor

time limit: 1Sec Memory limit: 128MB Submit: 3994 solve: 2355
 Title Description
 Find the interval[a,b]Prime factorization of all integers in. 

Tips


Sift out all primes before decomposing. 

Data scale and agreement 







input
 Enter two integers a，b.  

2< =a< =b< =10000

output
 Each line outputs a decomposition of a number, as shown in k=a1*a2*a3...(a1< =a2< =a3...，k From small to large)(See the sample for details) 
sample input 
3 10
 sample output 
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

analysis

• Just try to divide small data. Don't think too much.
• If it is big data, consider using the Angstrom screening method to screen out the possible quality factors, and directly operate with number and quality factors.
• It feels complicated. Because it is possible to repeat, in fact, it would be better to find out all the prime factors in python and then splice them (with '*'). At that time, I didn't think so much, so I directly and completely simulated it. Therefore, you will see repeated code (maybe my logic is confused)
• First, we find that the range of the prime factor is (2,math.ceil(math.sqrt(n)+1)), which is not much to explain. Mark whether the last flag is a prime factor.
• If a= i and a can divide i: prove that i is one of the prime factors of a, update a, judge whether a can be divided by i again: if so, print i and update a. Always note that if a is equal to i, it will definitely be the last, because the front has been screened out, which proves that a must be a prime number.
• However, if a is a prime number at the beginning or the prime factor is a prime number, we may not be able to filter it. Therefore, there is no mark at the end of the cycle, which also proves that he or the last bit is a prime number. Print him. In this way, in the update of a, a may become a floating-point number, so we need to integer int.
• The code logic is not difficult, but it is a little convoluted and not the clearest. This is also where I can continue to make progress and strive to write more understandable code in the future.

code

import math
def fuc(n):
    print(n,end=
    a = n # 
    while 1:
        flag = 0 # Is the tag the last one
        for i in range(2,math.ceil(math.sqrt(n)+1)):
            if a % i == 0 and a != i: # Prove not to be the last
                print(i,end="*")
                a = a / i # Because it can be divided, update a
                while a % i == 0: # Continue to divide
                    if a == i:
                        print(i)
                        flag = 1
                        break
                    print(i,end="*")
                    a = a/i
            if flag:
                break
            if a == i:
                print(i)
                flag = 1
                break
        if not flag: # Prove that the last number is prime
            print(int(a)) # Since division a becomes a floating point, it needs to be converted
        break
        
a,b = map(int,input().split())
for i in range(a,b+1):
    fuc(i)
            

Through screenshot

If there is any mistake, please correct it, welcome to communicate, thank you ♪ (♪ ω･) ﾉ