2022-02-12 daily clock in: problem fine brush

2022-02-12 Clock in every day ： Problem fine brush

Write it at the front

“ After these things are skilled , Maybe it's as plain as drinking water , But it can bring great happiness to beginners , I always thought , Can you always keep your enthusiasm as a beginner 、 focus , Determines how far you can go when you do something , How good can you do .” This series of articles is written by python To write , There are three sources of topics ： Not done before ;Leetcode secondary , Difficult and difficult questions ; Week title ; The classic topic of a topic , All codes have been AC. everyday 1-3 Avenue , Random analysis , I hope rain or shine , As a record of encouraging yourself to brush questions .

204. Count prime

Enumeration no longer gives , The biggest problem is that the correlation between numbers is not taken into account .

I want to learn something here 【 Egyptian sieve （ Eradorse sieve method ）】：

• consider x Prime number , Then its multiple 2x,3x… It must not be a prime number .
• Can be directly from x⋅x Start marker , because 2x,3x… These numbers must be in x Previously marked by multiples of other numbers , for example 2 All multiples of ,3 All multiples of .

class Solution:
    def countPrimes(self, n: int) -> int:
        #  from 2 Start checking , It was found that n-1（ Less than or equal to... Is detected n 了 ）
        isprime = [1 for i in range(0,n)]
        if len(isprime)<=1:
            return 0
        isprime[0]=isprime[1]=0
        for i in range(2,n):
            if isprime[i]:
                for j in range(i*i,n,i):
                    isprime[j]=0
        return sum(isprime)
        

【 Linear sieve 】 Our approach is more advanced , In order to eliminate redundant operations in the Egyptian sieve ：

• such as 45 Will be 3 and 5 Both numbers are marked at the same time , We expect $O(n)$ Complexity , That is, each number is determined only once . according to 《 Basic theorem of arithmetic 》：【 Every composite number can be uniquely written as the product of prime numbers 】. In other words , The product of multiple prime numbers can only form a unique composite number .
• No longer mark x All multiples of , Only the numbers in the prime number set and x The number multiplied by .
• For the problem of multiplying multiple prime numbers , It's not just a compound mark for prime numbers , But for each number , for example $8=4\ast 2$ in 4 Can't be ignored .
• Mark to... Each time $x\mathrm{m}\mathrm{o}\mathrm{d}prime{s}_i==0$, Because if x You can divide a prime number , So for composite numbers $x\ast prime{s}_i=x/prime{s}_i\ast prime{s}_{i+1}$, That is, there must be a larger number behind it so that it can be marked . Another blogger said in his introduction that the purpose is 【 Sift him out with the smallest quality factor 】.

class Solution:
    def countPrimes(self, n: int) -> int:
        #  from 2 Start checking , It was found that n-1（ Less than or equal to... Is detected n 了 ）
        isprime = [1 for i in range(0, n)]
        if len(isprime) <= 1:
            return 0
        isprime[0] = isprime[1] = 0
        primes = []
        for i in range(2, n):
            if isprime[i]:
                primes.append(i)
            for j in primes:
                if j*i < n :
                    isprime[i*j] = 0
                else:
                    break
                #  You must join before exiting 
                # 4 = 2*2
                if i % j == 0:
                    break
        return sum(isprime)
        

Smart Stefanie

The meaning of the question is to give a number S , Find the sum of divisors equals S All the numbers of .
Here's a theorem ：

The first contact is difficult to understand , for instance ：$360=2^3\times 3^2\times 5$ , The sum of its divisors is $(1+2^1+2^2+2^3)\times (1+3^1+3^2)\times (1+5^1)$.

We can enumerate （ Will timeout ） Method to check each number , It can also be decomposed by searching ：

• If the current number can be expressed as a prime number that has not been searched and 1 And , Then the product of the number searched before and this prime number conforms to the meaning of the question .
• For every prime number that has not been searched and whose square is less than the current number , Then enumerate all that may conform to the meaning of the topic ai Perform a recursive search .

It's really not written , The code is This blogger's link ：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100000
int p[N+5],cnt,s,ans,num[N+5];
bool flag[N+5];
void getprime()
{
    
	for(int i=2;i<=N;i++)
	{
    
		if(!flag[i]) p[++cnt]=i;
		for(int j=1; i*p[j]<=N; j++)
		{
    
			flag[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
bool isprime(int x)
{
    
	if(x==1) return false;
	if(x<=N) return !flag[x];
	for(int i=1;p[i]*p[i]<=x;i++)
		if(x%p[i]==0) return false;
	return true;
}
void dfs(int last,int now,int tot)
{
    
// now->summ, tot->left, last->pos 
	if(tot==1){
     num[++ans]=now; return; }
	if(tot-1>p[last]&&isprime(tot-1))
		num[++ans]=now*(tot-1);
	for(int i=last+1; p[i]*p[i]<=tot; i++)
		for(int tnum=p[i]+1,t=p[i]; tnum<=tot; t*=p[i],tnum+=t)
			if(tot%tnum==0)
				dfs(i,now*t,tot/tnum);
}
int main()
{
    
	getprime();
	while(scanf("%d",&s)!=EOF)
	{
    
		ans=0;
		dfs(0,1,s);
		cout<<ans<<endl;
		sort(num+1,num+ans+1);
		for(int i=1; i<=ans; i++)
			printf("%d%c",num[i],i==ans?'\n':' ');
	}
}