[weekly pit] positive integer factorization prime factor + [solution] calculate the sum of prime numbers within 100

Zero basis python Introductory tutorial ：python666.cn

Hello everyone , Welcome to Crossin Programming classroom of ！

This week we continue to work with “ Prime number ” screwing .

Please listen to ：

Divide a positive integer into prime factors . If it's a prime number , The output “ This is a prime number ”

About Decomposing prime factor ： Each sum can be written in the form of multiplication of several prime numbers , Each prime number is a factor of the sum , Express a sum in the form of multiplication of prime factors , It's called the decomposition prime factor . The decomposition prime factor is only for the sum .

for example ：

Input 90, Output 2 3 3 5

Input  23, Output This is a prime number

Detailed answers and reference codes will be given in the next column , You can also refer to the code in the message of other students .

I look forward to your answers , I hope you can complete the whole series .

Simple code can be submitted directly in the message , Long code is recommended  paste.ubuntu.com  or  

codeshare.io  And other code sharing sites , Just copy the code and save it , You can get a share address , Very convenient .

For past questions, click the collection at the beginning of the article “ Every Monday ” Enter the view .

---

【 answer 】 Calculation 100 Sum of prime numbers within

The general idea of this question is ：

 Traverse  2~100:
     Judge whether the current number is a prime number 
     If it's a prime number , Add the value to the result 
 Output results 

The basic method of judging prime numbers is ：

 Traverse  2~ Number to be judged :
     Determine whether it can be divided by the current number 
     If you can divide , Is not a prime number 
 If there is nothing divisible after traversal , Is a prime number 

however , There are many places that can be optimized , Let the program get the result with less calculation times . For example, judge a number N Whether prime numbers do not need to be traversed 2~N, Just go to √N that will do .

You can look at the last issue @ A stone The answer to , It is a good optimization scheme ：

def primeSum(N=100):  
    initial=[]    
    prime=0    
    node=int(N**0.5)+1    
    for i in range(2,node):       
        if 0 not in [i%pr for pr in initial]:            
            prime+=i            
            initial.append(i)    
    for i in range(node,N):
        if 0 not in [i%pr for pr in initial]:
            prime+=i    
    return prime
print(primeSum())

I mentioned it last time , Let's talk about an interesting solution . The idea of this solution is contrary to the conventional , It's not to judge who is prime , It's to get rid of those that are not prime numbers ：

 establish  2~100  A list of L
 If the list L There's still value in , Then continue the cycle :
     hold L[0] The value of is added to the result 
     For a list of L The elements in , Can be L[0] Don't divide everything , The rest becomes new L

Code ：

def primeSum(N=100):
    initial = list(range(2,N+1))
    prime = 0
    while len(initial) > 0:
        i = initial[0]
        prime += i
        initial = [num for num in initial if num % i != 0]
    return prime
print(primeSum())

The result is  1060

---

_ Previous articles are recommended _

【 Every Monday 】 Calculation 100 Sum of prime numbers within

---

If you need to know Paid premium courses And Teaching Q & a service

Please be there. Crossin Programming classroom of Internal reply : 666