首页 > 其他分享 >一个线性筛的多功能组合:筛法求质数+约数个数+约数和

一个线性筛的多功能组合:筛法求质数+约数个数+约数和

时间:2024-09-17 19:19:36浏览次数:14  
标签:约数 下标 筛法 质数 个数 因子 最小 素数 质因数

F:\BC\2024\9>main1
活动代码页: 936
2  2X2=4
3  3X2=6  3X3=9
4X2=8
5  5X2=10  5X3=15  5X5=25
6X2=12
7  7X2=14  7X3=21  7X5=35  7X7=49
8X2=16
9X2=18  9X3=27
10X2=20
11  11X2=22  11X3=33  11X5=55  11X7=77  11X11=121
12X2=24
13  13X2=26  13X3=39  13X5=65  13X7=91  13X11=143  13X13=169
14X2=28
15X2=30  15X3=45
16X2=32
17  17X2=34  17X3=51  17X5=85  17X7=119  17X11=187  17X13=221  17X17=289
18X2=36
19  19X2=38  19X3=57  19X5=95  19X7=133  19X11=209  19X13=247
20X2=40
21X2=42  21X3=63
22X2=44
23  23X2=46  23X3=69  23X5=115  23X7=161  23X11=253  23X13=299
24X2=48
25X2=50  25X3=75  25X5=125
26X2=52
27X2=54  27X3=81
28X2=56
29  29X2=58  29X3=87  29X5=145  29X7=203
30X2=60
31  31X2=62  31X3=93  31X5=155  31X7=217
32X2=64
33X2=66  33X3=99
34X2=68
35X2=70  35X3=105  35X5=175
36X2=72
37  37X2=74  37X3=111  37X5=185  37X7=259
38X2=76
39X2=78  39X3=117
40X2=80
41  41X2=82  41X3=123  41X5=205  41X7=287
42X2=84
43  43X2=86  43X3=129  43X5=215
44X2=88
45X2=90  45X3=135
46X2=92
47  47X2=94  47X3=141  47X5=235
48X2=96
49X2=98  49X3=147  49X5=245
50X2=100
51X2=102  51X3=153
52X2=104
53  53X2=106  53X3=159  53X5=265
54X2=108
55X2=110  55X3=165  55X5=275
56X2=112
57X2=114  57X3=171
58X2=116
59  59X2=118  59X3=177  59X5=295
60X2=120
61  61X2=122  61X3=183
62X2=124
63X2=126  63X3=189
64X2=128
65X2=130  65X3=195
66X2=132
67  67X2=134  67X3=201
68X2=136
69X2=138  69X3=207
70X2=140
71  71X2=142  71X3=213
72X2=144
73  73X2=146  73X3=219
74X2=148
75X2=150  75X3=225
76X2=152
77X2=154  77X3=231
78X2=156
79  79X2=158  79X3=237
80X2=160
81X2=162  81X3=243
82X2=164
83  83X2=166  83X3=249
84X2=168
85X2=170  85X3=255
86X2=172
87X2=174  87X3=261
88X2=176
89  89X2=178  89X3=267
90X2=180
91X2=182  91X3=273
92X2=184
93X2=186  93X3=279
94X2=188
95X2=190  95X3=285
96X2=192
97  97X2=194  97X3=291
98X2=196
99X2=198  99X3=297
100X2=200
101  101X2=202
102X2=204
103  103X2=206
104X2=208
105X2=210
106X2=212
107  107X2=214
108X2=216
109  109X2=218
110X2=220
111X2=222
112X2=224
113  113X2=226
114X2=228
115X2=230
116X2=232
117X2=234
118X2=236
119X2=238
120X2=240
121X2=242
122X2=244
123X2=246
124X2=248
125X2=250
126X2=252
127  127X2=254
128X2=256
129X2=258
130X2=260
131  131X2=262
132X2=264
133X2=266
134X2=268
135X2=270
136X2=272
137  137X2=274
138X2=276
139  139X2=278
140X2=280
141X2=282
142X2=284
143X2=286
144X2=288
145X2=290
146X2=292
147X2=294
148X2=296
149  149X2=298

151

157

163

167

173

179

181

191

193

197

199

211

223

227

229

233

239

241

251

257

263

269

271

277

281

283

293


=========================
0:
下标为0的素数是2
1:
下标为1的素数是3
2:
下标为2的素数是5
分析2是不是素数,值为0则是素数 0
2中最小质因数的个数是1个
2去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
2的因子的个数是2个
2的因子和是3


3:
下标为3的素数是7
分析3是不是素数,值为0则是素数 0
3中最小质因数的个数是1个
3去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
3的因子的个数是2个
3的因子和是4


4:
下标为4的素数是11
分析4是不是素数,值为0则是素数 1
4中最小质因数的个数是2个
4去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
4的因子的个数是3个
4的因子和是7


5:
下标为5的素数是13
分析5是不是素数,值为0则是素数 0
5中最小质因数的个数是1个
5去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
5的因子的个数是2个
5的因子和是6


6:
下标为6的素数是17
分析6是不是素数,值为0则是素数 1
6中最小质因数的个数是1个
6去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是4
6的因子的个数是4个
6的因子和是12


7:
下标为7的素数是19
分析7是不是素数,值为0则是素数 0
7中最小质因数的个数是1个
7去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
7的因子的个数是2个
7的因子和是8


8:
下标为8的素数是23
分析8是不是素数,值为0则是素数 1
8中最小质因数的个数是3个
8去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
8的因子的个数是4个
8的因子和是15


9:
下标为9的素数是29
分析9是不是素数,值为0则是素数 1
9中最小质因数的个数是2个
9去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
9的因子的个数是3个
9的因子和是13


10:
下标为10的素数是31
分析10是不是素数,值为0则是素数 1
10中最小质因数的个数是1个
10去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是6
10的因子的个数是4个
10的因子和是18


11:
下标为11的素数是37
分析11是不是素数,值为0则是素数 0
11中最小质因数的个数是1个
11去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
11的因子的个数是2个
11的因子和是12


12:
下标为12的素数是41
分析12是不是素数,值为0则是素数 1
12中最小质因数的个数是2个
12去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是4
12的因子的个数是6个
12的因子和是28


13:
下标为13的素数是43
分析13是不是素数,值为0则是素数 0
13中最小质因数的个数是1个
13去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
13的因子的个数是2个
13的因子和是14


14:
下标为14的素数是47
分析14是不是素数,值为0则是素数 1
14中最小质因数的个数是1个
14去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是8
14的因子的个数是4个
14的因子和是24


15:
下标为15的素数是53
分析15是不是素数,值为0则是素数 1
15中最小质因数的个数是1个
15去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是6
15的因子的个数是4个
15的因子和是24


16:
下标为16的素数是59
分析16是不是素数,值为0则是素数 1
16中最小质因数的个数是4个
16去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
16的因子的个数是5个
16的因子和是31


17:
下标为17的素数是61
分析17是不是素数,值为0则是素数 0
17中最小质因数的个数是1个
17去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
17的因子的个数是2个
17的因子和是18


18:
下标为18的素数是67
分析18是不是素数,值为0则是素数 1
18中最小质因数的个数是1个
18去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是13
18的因子的个数是6个
18的因子和是39


19:
下标为19的素数是71
分析19是不是素数,值为0则是素数 0
19中最小质因数的个数是1个
19去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
19的因子的个数是2个
19的因子和是20


20:
下标为20的素数是73
分析20是不是素数,值为0则是素数 1
20中最小质因数的个数是2个
20去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是6
20的因子的个数是6个
20的因子和是42
 

  #include<iostream>
 using namespace std;

 #define n 100000
 #define N n+1
 
 int m;
 int a[N],b[N],c[N],d[N];  
 //a[i]  表示i是否为质数
 //b[i]  表示第i个质数 
 //c[i]  表示i的最小质因数个数 
 //d[i]  表示i的最小质因数
 
 int f[N],g[N]; //f[i]表示i的约数个数 g[i]表示i的约数和
 
 void init()
 {
	 f[1]=g[1]=1;
	 for(int i=2;i<=n;i++){
	 	if(!a[i]){
            if(i<300)
                printf("%d  ",i);
			b[m++]=i;
			c[i]=1,f[i]=2;
			d[i]=1,g[i]=i+1;
		}
		for(int j=0;j<m&&b[j]*i<=n;j++){
			int k=b[j];
			a[i*k]=1;
            if(i*k<300)
                printf("%dX%d=%d  ",i,k,i*k);
			if(i%k==0){
				c[i*k]=c[i]+1;
				f[i*k]=f[i]/c[i*k]*(c[i*k]+1);
				d[i*k]=d[i];
				g[i*k]=g[i]*k+d[i];
				break;
			}
			else{
				c[i*k]=1;
				f[i*k]=2*f[i];	                
				d[i*k]=g[i];
				g[i*k]=g[i]*(k+1);
			}            
		}  
        if(i<300)     
            puts("");
	 }

cout<<"========================="<<endl;
for(int x=0;x<=20;x++){
    cout<<x<<":"<<endl;
    printf("下标为%d的素数是%d\n",x,b[x]);
    if(x==0||x==1)continue;
    
     printf("分析%d是不是素数,值为0则是素数 %d\n",x,a[x]);     
     printf("%d中最小质因数的个数是%d个\n",x,c[x]);
     printf("%d去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是%d\n",x,d[x]);
	 printf("%d的因子的个数是%d个\n",x,f[x]);
     printf("%d的因子和是%d\n",x,g[x]);
     puts("");
     puts("");
}

 }

 int main()
 {
    system("chcp 936");
	 init();
	
	 int x;
	 scanf("%d",&x);
     printf("下标为%d的素数是%d\n",x,b[x]);
     printf("分析%d是不是素数,值为0则是素数 %d\n",x,a[x]);     
     printf("%d中最小质因数的个数是%d个\n",x,c[x]);
     printf("%d去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是%d\n",x,d[x]);
	 printf("%d的因子的个数是%d个\n",x,f[x]);
     printf("%d的因子和是%d\n",x,g[x]);
     puts("");
     puts("");
	 return 0;
 }
/*
输入30
答案是 8和 72
1 2 3 5 6 10 15 30
*/


F:\BC\2024\9>main1
活动代码页: 936
=========================
0:
下标为0的素数是2
1:
下标为1的素数是3
2:
下标为2的素数是5
分析2是不是素数,值为0则是素数 0
2中最小质因数的个数是1个
2去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
2的因子的个数是2个
2的因子和是3


3:
下标为3的素数是7
分析3是不是素数,值为0则是素数 0
3中最小质因数的个数是1个
3去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
3的因子的个数是2个
3的因子和是4


4:
下标为4的素数是11
分析4是不是素数,值为0则是素数 1
4中最小质因数的个数是2个
4去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
4的因子的个数是3个
4的因子和是7


5:
下标为5的素数是13
分析5是不是素数,值为0则是素数 0
5中最小质因数的个数是1个
5去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
5的因子的个数是2个
5的因子和是6


6:
下标为6的素数是17
分析6是不是素数,值为0则是素数 1
6中最小质因数的个数是1个
6去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是4
6的因子的个数是4个
6的因子和是12


7:
下标为7的素数是19
分析7是不是素数,值为0则是素数 0
7中最小质因数的个数是1个
7去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
7的因子的个数是2个
7的因子和是8


8:
下标为8的素数是23
分析8是不是素数,值为0则是素数 1
8中最小质因数的个数是3个
8去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
8的因子的个数是4个
8的因子和是15


9:
下标为9的素数是29
分析9是不是素数,值为0则是素数 1
9中最小质因数的个数是2个
9去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
9的因子的个数是3个
9的因子和是13


10:
下标为10的素数是31
分析10是不是素数,值为0则是素数 1
10中最小质因数的个数是1个
10去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是6
10的因子的个数是4个
10的因子和是18


11:
下标为11的素数是37
分析11是不是素数,值为0则是素数 0
11中最小质因数的个数是1个
11去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
11的因子的个数是2个
11的因子和是12


12:
下标为12的素数是41
分析12是不是素数,值为0则是素数 1
12中最小质因数的个数是2个
12去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是4
12的因子的个数是6个
12的因子和是28


13:
下标为13的素数是43
分析13是不是素数,值为0则是素数 0
13中最小质因数的个数是1个
13去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
13的因子的个数是2个
13的因子和是14


14:
下标为14的素数是47
分析14是不是素数,值为0则是素数 1
14中最小质因数的个数是1个
14去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是8
14的因子的个数是4个
14的因子和是24


15:
下标为15的素数是53
分析15是不是素数,值为0则是素数 1
15中最小质因数的个数是1个
15去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是6
15的因子的个数是4个
15的因子和是24


16:
下标为16的素数是59
分析16是不是素数,值为0则是素数 1
16中最小质因数的个数是4个
16去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
16的因子的个数是5个
16的因子和是31


17:
下标为17的素数是61
分析17是不是素数,值为0则是素数 0
17中最小质因数的个数是1个
17去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
17的因子的个数是2个
17的因子和是18


18:
下标为18的素数是67
分析18是不是素数,值为0则是素数 1
18中最小质因数的个数是1个
18去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是13
18的因子的个数是6个
18的因子和是39


19:
下标为19的素数是71
分析19是不是素数,值为0则是素数 0
19中最小质因数的个数是1个
19去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是1
19的因子的个数是2个
19的因子和是20


20:
下标为20的素数是73
分析20是不是素数,值为0则是素数 1
20中最小质因数的个数是2个
20去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是6
20的因子的个数是6个
20的因子和是42


99
下标为99的素数是541
分析99是不是素数,值为0则是素数 1
99中最小质因数的个数是2个
99去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是12
99的因子的个数是6个
99的因子和是156

  #include<iostream>
 using namespace std;

 #define n 100000
 #define N n+1
 
 int m;
 int a[N],b[N],c[N],d[N];  
 //a[i]  表示i是否为质数
 //b[i]  表示第i个质数 
 //c[i]  表示i的最小质因数个数 
 //d[i]  去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],
 
 int f[N],g[N]; //f[i]表示i的约数个数 g[i]表示i的约数和
 
 void init()
 {
	 f[1]=g[1]=1;
	 for(int i=2;i<=n;i++){
	 	if(!a[i]){
			b[m++]=i;
			c[i]=1,f[i]=2;
			d[i]=1,g[i]=i+1;
		}
		for(int j=0;j<m&&b[j]*i<=n;j++){
			int k=b[j];
			a[i*k]=1;
			if(i%k==0){
				c[i*k]=c[i]+1;
				f[i*k]=f[i]/c[i*k]*(c[i*k]+1);
				d[i*k]=d[i];
				g[i*k]=g[i]*k+d[i];
				break;
			}
			else{
				c[i*k]=1;
				f[i*k]=2*f[i];	                
				d[i*k]=g[i];
				g[i*k]=g[i]*(k+1);
			}
		}
	 }

cout<<"========================="<<endl;
for(int x=0;x<=20;x++){
    cout<<x<<":"<<endl;
    printf("下标为%d的素数是%d\n",x,b[x]);
    if(x==0||x==1)continue;
    
     printf("分析%d是不是素数,值为0则是素数 %d\n",x,a[x]);     
     printf("%d中最小质因数的个数是%d个\n",x,c[x]);
     printf("%d去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是%d\n",x,d[x]);
	 printf("%d的因子的个数是%d个\n",x,f[x]);
     printf("%d的因子和是%d\n",x,g[x]);
     puts("");
     puts("");
}

 }

 int main()
 {
    system("chcp 936");
	 init();
	
	 int x;
	 scanf("%d",&x);
     printf("下标为%d的素数是%d\n",x,b[x]);
     printf("分析%d是不是素数,值为0则是素数 %d\n",x,a[x]);     
     printf("%d中最小质因数的个数是%d个\n",x,c[x]);
     printf("%d去掉此数的最小质因子得到的数[注意,最小质因子可能有多个],这个数的因子和是%d\n",x,d[x]);
	 printf("%d的因子的个数是%d个\n",x,f[x]);
     printf("%d的因子和是%d\n",x,g[x]);
     puts("");
     puts("");
	 return 0;
 }
/*
输入30
答案是 8和 72
1 2 3 5 6 10 15 30
*/

标签:约数,下标,筛法,质数,个数,因子,最小,素数,质因数
From: https://blog.csdn.net/laocooon/article/details/142313788

相关文章

  • 【MySQL】基础部分——DDL,DML,DQL,DCL,函数,约数,多表查询,事务
    个人学习记录,供以后回顾和复习ubuntu下安装使用1.DDL,DML,DQL,DCLDDL数据库表DML增改删DQL条件查询分组查询排序查询分页查询DCL管理用户权限控制2.函数字符串函数数值函数日期函数流程函数3.约束4.多表查询多表关系内连接外连接自连接联合查询union子查询标量子查询......
  • 「数学::质数」埃氏筛|欧拉筛(埃拉托斯特尼筛法|线性筛法)/ LeetCode 204(C++)
    目录概述1.埃氏筛思路复杂度Code2.欧拉筛(线性筛)思路复杂度Code总结概述上一节我们介绍了对判断一个数是否为质数的方法:「数学::质数」试除法/LuoguP5736(C++)那如果我们期望输出一个范围内的所有质数,使用试除法的时间复杂度是n√n,怎么办呢?LeetCode204:给定整......
  • P3327 [SDOI2015] 约数个数和
    [SDOI2015]约数个数和题目描述设\(d(x)\)为\(x\)的约数个数,给定\(n,m\),求\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]输入格式输入文件包含多组测试数据。第一行,一个整数\(T\),表示测试数据的组数。接下来的\(T\)行,每行两个整数\(n,m\)。输出格式\(T\)行,每行一个整数,表......
  • 【AcWing】866~868. 质数
    #include<iostream>#include<math.h>usingnamespacestd;intn;boolis_prime(intx){if(x<2)returnfalse;for(inti=2;i<=x/i;i++){if(x%i==0)returnfalse;}returntrue;}intmain(){cin>>n;......
  • 找质数完整版?(小白的练习)
    目的很简单,学到哪就稍微用一下刚学的知识,下面是我的代码(其中有些步骤可以简化,就比如在search函数中用指针没什么意义,因为我只需要return“tureorfalse”如果用指针其实是杀鸡用牛刀,不过只是练习一下学的,所以目的不同代码自然不同,欢迎指教#include#includevoidsearch(int......
  • 质数
    1.质数定义我们这样定义质数:如果自然数$p>1$的因数只有1和它本身,那么$p$是质数。不是质数,就是合数。质数有很多美妙的性质,比如:如果一个数是质数,那么它是自然数。如果一个数是质数,那么它不是合数。如果一个数是质数,那么它大于等于2。2.判断\(n\)是否为质数的方法2.1枚......
  • 经典小题——生成质数
    在写程序之前,我们先想想什么是质数1.是一个大于一的自然数2.不能被任何数整除(除了1和自身)那我们如何检测呢?可以用for循环的方法(其他也行,方法不唯一),因为不能除以自身,所以最少的结果也是2(因为自身除以自身等于一),那就可以写for(b=2;b<a/2;b++),总之我们想做好这个程序,只有创建一......
  • Python 判断质数的另一种方法
    质数就是大于等于2且只能被它本身及1整除的数,百度上关于质数的性质和相关的公式还有很多,不过有点高深难懂,尤其是对我这个数学不好的人来说。网上python判断质数的方法大多是下面这种:frommathimportsqrtdefis_prime(n):ifn==1: print("此数为不质数")......
  • 第五章习题3-输入两个正整数m和n,求其最大公约数和最小公倍数
     ......
  • 7-3 sdut-最大公约数和最小公倍数
    给定2个正整数,求它们的最大公约数和最小公倍数,并输出。输入格式:输入有若干组。每组数据,在一行中给出两个正整数M和N(≤1000),中间有1个空格。输出格式:对于每组输入,在一行中顺序输出M和N的最大公约数和最小公倍数,两数字间以1个空格分隔。输入样例:181220153926576......