质数

Posted on Edited on
密码学
1
C:\blog\source\_posts\质数.assets\

一、获取质数集的方法

注：一些个人收集的方法，以下代码未特定说明则均在 linux 操作系统上编译运行

1、遍历

参考链接： C语言：找出10000以内所有的素数（质数）_求10000以内正整数中最大素数？_是彦歆呀嘻嘻哈哈的博客-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>

int main()
{
    int a,b,i,j,k=0;
    FILE *fp=NULL;
    fp = fopen("./1.txt","w");  //打开当前目录下的1.txt文件，没有则自动生成1.txt文件

    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&b);
    
    for(i=2;i<=b;i++){
        for(j=2;j*j<=i;j++){
            if(i%j==0)    //判断i是否能被1和本身以外的数整除，%表示求余
                break;    //break跳出第二个for循环
        }
        if(j*j>i){
            fprintf(fp,"%d,",i);
            k++;          //每增加一个素数k就加1
            if(k%20==0)   //一行打印10个数之后换行
                fprintf(fp,"\n");
        }
    }
    printf("\n  1 ~ %d 中含有 %d 个质数\n\n",b,k);
    return 0;
}

分析：

1
2
3
4
5
6
7
8
9
#以上代码计算的核心是以下两行代码
    for(i=2;i<=b;i++){
        for(j=2;j*j<=i;j++){
            
#这种遍历方式首先遍历一遍2-n ，计算复杂度大致为 O(n)
#其次遍历一遍2-√n，计算复杂度大致为 O(√n)
#所以总的计算复杂度大致为 O(n√n)
#空间复杂度O(0)
#我数学不太行，有错请指正

问：产生的1.txt有什么用？

答：便于python处理


2、遍历优化

对我们得到的质数集进行观察我们可以发现：除2外，所有质数的末尾必是1、3、7、9中的一个，那我们可以对上面的算法进行以下优化：

(同理还可以知道：一个大于等于5的素数模12得到的值必是1、5、7、11)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>

int main()
{
    int a,b,c,i,j,k=0;
    FILE *fp=NULL;
    fp = fopen("./1.txt","w");  //打开当前目录下的1.txt文件，没有则自动生成1.txt文件

    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&b);
    
    //将2、3、5写入文件，后续我们只需要考虑末尾为1、3、7、9的情况
    fprintf(fp,"2,3,5,\n");
    
    for(i=3;i<=b;i++){
        c = i%10;
        if(c!=1 && C!=3 && c!=7 && c!=9)
            continue;
    	
        for(j=2;j*j<=i;j++){
            if(i%j==0)    //判断i是否能被1和本身以外的数整除，%表示求余
                break;    //break跳出第二个for循环
        }
        
        if(j*j>i){
            fprintf(fp,"%d,",i);
            k++;          //每增加一个素数k就加1
            if(k%20==0)   //一行打印10个数之后换行
                fprintf(fp,"\n");
        }
    }
    k+=3;                 //2、3、5还没算进来，得加3
    printf("\n  1 ~ %d 中含有 %d 个质数\n\n",b,k);
    return 0;
}

经过一轮筛选，0-9可以筛掉6个数字，1-6/10=0.4，所以计算复杂度大致为O(0.4*n√n)，空间复杂度O(0)

3、素数性质1

其实这个性质类似于我上面说的除2、3、5外，素数末尾必定是1、3、7、9

参考链接：求素数三种简单方法 - 知乎 (zhihu.com)

1
2
3
# 链接可以不用看，我这里给出摘要：
  1、除 2、3 外，素数模 6 等于 1 或 5 
  2、一个模6等于1或5的数不一定是素数，例：25%6=1但25不是素数

利用以上性质，我们可以继续优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>

int main()
{
    int a,b,c,d,e,i,j,k=0;
    FILE *fp=NULL;
    fp = fopen("./1.txt","w");  //打开当前目录下的1.txt文件，没有则自动生成1.txt文件

    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&b);
    
    //将2、3、5写入文件，后续我们只需要考虑末尾为1、3、7、9的情况
    fprintf(fp,"2,3,5,\n");
    
    for(i=3;i<=b;i++){
        c = i%10;
        d = i%12;
        e = i%6;
        if(c!=1 && c!=3 && c!=7 && c!=9)
            continue;
    	if(d!=1 && d!=5 && d!=7 && d!=11)
            continue;
        if(e!=1 && e!=5)
            continue;
        
        for(j=2;j*j<=i;j++){
            if(i%j==0)    //判断i是否能被1和本身以外的数整除，%表示求余
                break;    //break跳出第二个for循环
        }
        
        if(j*j>i){
            fprintf(fp,"%d,",i);
            k++;          //每增加一个素数k就加1
            if(k%20==0)   //一行打印10个数之后换行
                fprintf(fp,"\n");
        }
    }
    k+=3;                 //2、3、5还没算进来，得加3
    printf("\n  1 ~ %d 中含有 %d 个质数\n\n",b,k);
    return 0;
}

注：数字大了会出问题

以上的优化方式可以自行探索添加、但再加就不礼貌了，速率也不会提升多少，以上代码的空间代价几乎没有，内存不用存大数组。

4、筛选法求质数

参考链接1：求质数的几种算法 - ChuckLu - 博客园 (cnblogs.com)

参考链接2：Bitmap C语言实现_geditzh的博客-CSDN博客

参考链接3：C/C++手动实现sqrt() - cnwanglu - 博客园 (cnblogs.com)

个人理解：典型的空间换时间算法，求大范围素数时需要在内存中建立大数组，空间复杂度O(n)

1
2
3
4
5
6
# 流程：假设要找200以内的质数，
  1、13² < 200 < 14²
  2、建立一个数组arr，存储0-200这200个数字
  3、遍历2-14，删除数组arr内的所有遍历数的倍数(在代码实现中 删除 ≠ 释放空间)
     (从2开始，先删除所有2的倍数，再删除所有3的倍数...删除所有14的倍数)
  4、得到一个全部为素数的数组

筛选法代码如下：(运用到bitmap的话，可以节约巨大的空间，一个int32位，一个bit一位，节约31/32左右的空间)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>
#include <stdlib.h>
// #include <math.h>  无语，linux不支持<math.h>头文件，只能自己写开根号函数

#define SHIFT 5
#define MASK 0x1F

void set(int n,int *arr);     //防止看不懂，照搬链接 2 中的函数，不懂先去看链接 2
void clr(int n, int *arr);    //防止看不懂，照搬链接 2 中的函数，不懂先去看链接 2
int test(int n, int *arr);    //防止看不懂，照搬链接 2 中的函数，不懂先去看链接 2
void start(int *arr);         //简单调用
void myexit(int *ptr);        //不做解释
float mysqrt(float x);        //防止看不懂，照搬链接 3 中的函数，不懂先去看链接 3

int main()
{
    int i, j, k, num, space, *arr, sqrt_b;
    float sqrt_a;
    FILE *fp=NULL;
    fp = fopen("./1.txt","w");  //打开当前目录下的1.txt文件，没有则自动生成1.txt文件

    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&num);
    
    sqrt_a = mysqrt(num);
    sqrt_b = (int)sqrt_a + 1;
    printf("\n(int)sqrt(%d)+1 = %d\n",num,sqrt_b);
    
    space = sqrt_b*sqrt_b / 32 + 1;  //--/为了防止堆溢出，这里就开大了点/--//
    arr = (int *)malloc(sizeof(int) * space);

    //--/初始化bit位为0,表示一个 0-所输入数值 内的所有数值均存在的数组/--//
    for (i = 0; i <= num; i ++)
        clr(i, arr);
    
    start(arr);    //1-7中1、4、6不为质数，剔除
    
    for(i=2;i<=sqrt_b;i++){    //操作bitmap，筛选删除数的倍数
        for(j=i;(j<=num/i || j<=sqrt_b);j++){
            k = i*j;
            set(k,arr);
            if (!test(k, arr)) {
                printf("bitmap操作失败 - %d\n",k);
                myexit(arr);
            }
        }
    }

    // 设置num的比特位为1
    k=0;
    for(i=0;i<=num;i++){
        if (!test(i, arr)) {
            k++;
            fprintf(fp,"%d,",i);
            if(k%20==0)
                fprintf(fp,"\n");
        }
    }
    
    printf("\n  1~%d 中有 %d 个质数\n\n",num,k);
    
    free(arr);  //--/一开始我没写free(),出事故了,想看事故什么样,注释该行就可以/--//
                //--/重启解决99%的问题/--//
    
    return 0;
}

void set(int n,int *arr)
{
    int index_loc, bit_loc;

    index_loc = n >> SHIFT; // 等价于n / 32
    bit_loc = n & MASK;    // 等价于n % 32 。 h%2^n = h & (2^n -1)

    //--/先左移1，再或等于数组，优先级/--//
    arr[index_loc] |= 1 << bit_loc;
}

//--/初始化bitmap，将所有字节置为0/--//
void clr(int n, int *arr)
{
    int index_loc;
    index_loc = n >> SHIFT;
    arr[index_loc] &= 0;    //bit为0表示该数存在，bit为1代表该数被删除
}

//--/测试bitmap中的bit位是否被置为1/--//
int test(int n, int *arr)
{
    int i, flag;
    i = 1 << (n & MASK);
    flag = arr[n >> SHIFT] & i;
    return flag;
}

void start(int *arr)
{
    set(0,arr);    //1-7中0、1、4、6不为质数
    if (!test(0, arr)) {    //这些if(!test(,)){}都可直接删除
        printf("bitmap操作失败 - 0\n");
        myexit(arr);
    }
    
    set(1,arr);   
    if (!test(1, arr)) {
        printf("bitmap操作失败 - 1\n");
        myexit(arr);
    }
    
    set(4,arr);
    if (!test(4, arr)) {
        printf("bitmap操作失败 - 4\n");
        myexit(arr);
    }
    
    set(6,arr);
    if (!test(6, arr)) {
        printf("bitmap操作失败 - 6\n");
        myexit(arr);
    }
}

void myexit(int *ptr)
{
    free(ptr);
    exit(0);
}

/*
 * function:神奇的算法实现sqrt()
 * author:wanglu
 */
float mysqrt(float x)
{

    float xhalf = 0.5f*x;
    int i = *(int*)&x; 
    
    if(!x) return 0;
    
    i = 0x5f375a86- (i>>1); // beautiful number
    x = *(float*)&i; 
    x = x*(1.5f-xhalf*x*x); // 牛顿迭代法，提高精度
    x = x*(1.5f-xhalf*x*x); // 牛顿迭代法，提高精度
    x = x*(1.5f-xhalf*x*x); // 牛顿迭代法，提高精度

    return 1/x;
}

分析：

1
2
3
4
5
6
7
8
9
#以上代码的核心是两条for循环:
    for(i=2;i<=sqrt_b;i++){    //操作bitmap，筛选删除数的倍数
        for(j=i;(j<=num/i || j<=sqrt_b);j++){

#两重for循环，最大均为√n+1,相乘约等于O(n)            
#计算量分析 n/2+n/3+...+n/√n 
#假设n=16不难看出计算量为16/2+16/3+16/4≈17，假设n=64不难看出计算量约为32+32/3+16+8≈66
#我这数学也不太行，反正计算复杂度应该是O(n)吧，n很大时比O(0.4*n√n)要好一些
#空间复杂度大概是O(n)bit，单位是bit很重要，比单位是int少了32倍空间

5、以质数为判断数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 理论：
  # 其实不难发现，要判断一个新的数是否为质数
  # 我们只需要将小于等于他的平方根的所有质数依次与该新数相模即可判断新数是否为质数
  # 之前的代码可知，2^20 = 1048576 中有 82025个质数，
  # 而√1048567 = 1024，1024以内有172个素数
  # 所以我们判断1048577是否为质数最多只要循环172+1次就够了
  # 而我们正常循环的话，需要大概1024次循环，效率能提高近6倍

# 实现
  # 有了以上的理论基础，我们可以按以下步骤编写代码
  # 1、因为要要操作数组，而我觉得python操作数组比较方便，所以现在用python进行编码
  # 2、定义两个数组arr[2,3]、brr[2,3]，用户输入想要取得的素数范围的最大值
  # 3、for循环生成arr[2,3,6n-1,6n+1]
  # 4、for循环遍历取出arr[]中的一个值x，求出√x
  # 5、以√x为range值for循环遍历brr[]依次取出小于√x的质数y，去与x相模(x%y)
  # 6、遍历完模值均不等于0，则将x用append()函数加入到brr中
  # 7、arr[]遍历完后将brr[]输出到1.txt文件即可

python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
##!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import string


def f_arr(num):
    global arr
    for i in range(1,num):
        arr.append(6*i-1)
        arr.append(6*i+1)

    while 1:    
        flag = arr[-1]    #取最后一个元素
        if(flag>user):
            arr.remove(flag)
        else:
            break

def f_brr(len_arr):
    global arr
    global brr
    for i in range(2,len_arr): 
        #print("arr[",i,"] =",arr[i])    #调试
        flag_this = 1   
        sqrt = int(math.sqrt(arr[i]))
        for j in range(0,sqrt):
            if(arr[i]%brr[j]==0):flag_this=0
        if(flag_this):brr.append(arr[i])
        

# 2、定义两个数组arr、brr，用户输入想要取得的素数范围的最大值
arr = [2,3]
brr = [2,3]
user = int(input("请输入一个值，我将输出0-该值之内的所有素数(例1048576):"))

# 3、for循环生成arr[2,3,6n-1,6n+1]
num = int(user/6)+3
f_arr(num)
#print(arr)           #查看arr生成情况

# 4、5、6
arr_len = int(len(arr))
f_brr(arr_len)
#print(brr)           #查看brr生成情况

# 7、arr[]遍历完后将brr[]输出到1.txt文件即可
brr_len = len(brr)
print("0 -",user,"之间有",brr_len,"个质数")
f = open("./1.txt",'w')
for i in range(0,brr_len):
    if(i%15==0):f.write("\n")
    f.write(str(brr[i])+',')
f.close()

对比分析：

1
2
# 1、遍历的数组从正整数集转变为arr[2,3,6*n-1,6*n+1]，减少了2/3的数字量
# 2、用于模的数组从[0-√x]转变为[0-√x的素数集]，效率能提高近6倍

image-20230308011256155

启发：

1
2
3
4
5
# 其实  4、筛选法求质数  也可以用质数集来快速清空bitmap中的非质数
# 不过前提是要在代码运行时实时生成一个现成的质数集给它用
# 实现的话  4、筛选法求质数  的效率按理来说应该还能提高近6倍
# 我的主要目的是的得到质数集，分析质数规律，找到求质数集的公式法
# 所以  4、筛选法求质数  的进一步优化就不做了

6、[2,3,6*n-1,6*n+1]与筛选法的结合

ae2a57711da6759ab83bfb6e1d3fe2f

1
2
3
4
5
6
7
8
9
10
11
# 理论
  # 从上图中我们不难发现[2,3,6*n-1,6*n+1]这个集合中的非质数是由质数相乘得来的
  # 所以我们可以遍历[2,3,6*n-1,6*n+1]
  # 将每个质数依次乘以大于等于自身的质数来清空[2,3,6*n-1,6*n+1]中的非质数

# 实践
  # 因为要操作数组，所以还是用python进行代码编写
  # 1、用户输入数值，生成 arr[] = [2,3,6*n-1,6*n+1]
  # 2、遍历 arr[]，从5开始，依次乘自身与比自身大的 arr[] 中的数
  # 3、arr.remove() 删除得到的 arr[] 中的非质数
  # 4、输出 arr[]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
##!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import string


def f_arr(num):
    global arr
    for i in range(1,num):
        arr.append(6*i-1)
        arr.append(6*i+1)

    while 1:    
        flag = arr[-1]    #取最后一个元素
        if(flag>user):
            arr.remove(flag)
        else:
            break

def clear_arr(arr):
    i = 2
    j = 2
    while (len(arr)/5) >= i+1 :    #除5是因为5是最小乘值
        arr_len0 = int(len(arr)/5 + 1)
        for j in range(i,arr_len0):
            num = arr[i]*arr[j]
            try:
                arr.remove(num)
            except:
                print(num,"is not in arr[]")    #调试
                break
        i += 1
    return arr
        

# 1、用户输入数值，生成 arr[] = [2,3,6*n-1,6*n+1]
arr = [2,3]
user = int(input("请输入一个值，我将输出0-该值之内的所有素数(例1048576):"))
num = int(user/6)+3
f_arr(num)
#print(arr)           #查看arr生成情况

# 2、遍历 arr[]，从5开始，依次乘自身与比自身大的 arr[] 中的数
# 3、arr.remove() 删除得到的 arr[] 中的非质数
brr = clear_arr(arr)

# 4、输出 brr[]
print(brr)

分析：

1
2
# 没有考虑到[2,3,6*n-1,6*n+1]中的非质数可能由两个以上的质数相乘得来
# 所以以上代码错误，不能用于生成素数集

image-20230308110246997

启发：

1
2
3
4
# 我们是否可以将数分段，然后逐段推导质数？
# 例如 0-5^2为一段、5^2-5^3为一段、5^3-5^4为一段......
# 然后逐段找规律求解质数集
# 甚至是用前一段的质数推算出后一段的所有质数(类似于数学公式)

完善：针对分析中的出错，这里给出以下完善代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
##!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import string


def f_arr(num):
    global arr
    for i in range(1,num):
        arr.append(6*i-1)
        arr.append(6*i+1)

    while 1:    
        flag = arr[-1]    #取最后一个元素
        if(flag>user):
            arr.remove(flag)
        else:
            break

def clear_arr(arr):
    global user
    global max

    for i in range(2,max+1):

        xy = len(arr)+1
        for a1 in range(2,xy):
            sum =1
            sum *= arr[a1]
            #print("sum =",sum)
            if(5*arr[a1]>=user):
                #print("a1 =",a1,"  sum =",sum)
                break

            for a2 in range(a1,xy):
                sum *= arr[a2]
                #print("sum2 =",sum)
                if(sum<user):
                    try:arr.remove(sum)
                    except:
                        nop = 1
                        #print(sum,"删除失败")
                        #sum /= arr[a2]
                        #continue
                else:
                    sum /= arr[a2]
                    break

                for a3 in range(a2,xy):
                    if(i<3):break
                    sum *= arr[a3]
                    #print("sum3 =",sum)
                    if(sum<user):
                        try:arr.remove(sum)
                        except:
                            nop = 1
                            #print(sum,"删除失败")
                            #sum /= arr[a3]
                            #continue
                    else:
                        sum /= arr[a3]
                        break

                    for a4 in range(a3,xy):
                        if(i<4):break
                        sum *= arr[a4]
                        if(sum<user):
                            try:arr.remove(sum)
                            except:
                                nop = 1
                                #print(sum,"删除失败")
                                #sum /= arr[a4]
                                #continue
                        else:
                            sum /= arr[a4]
                            break

                        for a5 in range(a4,xy):
                            if(i<5):break
                            sum *= arr[a5]
                            if(sum<user):
                                try:arr.remove(sum)
                                except:
                                    nop = 1
                                    #print(sum,"删除失败")
                                    #sum /= arr[a5]
                                    #continue
                            else:
                                sum /= arr[a5]
                                break
                            
                            for a6 in range(a5,xy):
                                if(i<6):break
                                sum *= arr[a6]
                                if(sum<user):
                                    try:arr.remove(sum)
                                    except:
                                        nop = 1
                                        #print(sum,"删除失败")
                                        #sum /= arr[a6]
                                        #continue
                                else:
                                    sum /= arr[a6]
                                    break

                                for a7 in range(a6,xy):
                                    if(i<7):break
                                    sum *= arr[a7]
                                    if(sum<user):
                                        try:arr.remove(sum)
                                        except:
                                            nop = 1
                                            #print(sum,"删除失败")
                                            #sum /= arr[a7]
                                            #continue
                                    else:
                                        sum /= arr[a7]
                                        break

                                    for a8 in range(a7,xy):
                                        if(i<8):break
                                        sum *= arr[a8]
                                        if(sum<user):
                                            try:arr.remove(sum)
                                            except:
                                                nop = 1
                                                #print(sum,"删除失败")
                                                #sum /= arr[a8]
                                                #continue
                                        else:
                                            sum /= arr[a8]
                                            break

                                        for a9 in range(a8,xy):
                                            if(i<9):break
                                            sum *= arr[a9]
                                            if(sum<user):
                                                try:arr.remove(sum)
                                                except:
                                                    nop = 1
                                                    #print(sum,"删除失败")
                                                    #sum /= arr[a9]
                                                    #continue
                                            else:
                                                sum /= arr[a9]
                                                break

                                            for a10 in range(a9,xy):
                                                if(i<10):break
                                                sum *= arr[a10]
                                                if(sum<user):
                                                    try:arr.remove(sum)
                                                    except:
                                                        nop = 1
                                                        #print(sum,"删除失败")
                                                        #sum /= arr[a10]
                                                        #continue
                                                else:
                                                    sum /= arr[a10]
                                                    break

                                                for a11 in range(a10,xy):
                                                    if(i<11):break
                                                    sum *= arr[a11]
                                                    if(sum<user):
                                                        try:arr.remove(sum)
                                                        except:
                                                            nop = 1
                                                            #print(sum,"删除失败")
                                                            #sum /= arr[a11]
                                                            #continue
                                                    else:
                                                        sum /= arr[a11]
                                                        break

                                                    for a12 in range(a11,xy):
                                                        if(i<12):break
                                                        sum *= arr[a12]
                                                        if(sum<user):
                                                            try:arr.remove(sum)
                                                            except:
                                                                nop = 1
                                                                #print(sum,"删除失败")
                                                                #sum /= arr[a12]
                                                                #continue
                                                        else:
                                                            sum /= arr[a12]
                                                            break

                                                        for a13 in range(a12,xy):
                                                            if(i<13):break
                                                            sum *= arr[a13]
                                                            if(sum<user):
                                                                try:arr.remove(sum)
                                                                except:
                                                                    nop = 1
                                                                    #print(sum,"删除失败")
                                                                    #sum /= arr[a13]
                                                                    #continue
                                                            else:
                                                                sum /= arr[a13]
                                                                break
                                                            sum /= arr[a13]
                                                        sum /= arr[a12]
                                                    sum /= arr[a11]
                                                sum /= arr[a10]
                                            sum /= arr[a9]
                                        sum /= arr[a8]
                                    sum /= arr[a7]                      
                                sum /= arr[a6] 
                            sum /= arr[a5] 
                        sum /= arr[a4] 
                    sum /= arr[a3]                                       
                sum /= arr[a2]                                         
    return arr

# 1、用户输入数值，生成 arr[] = [2,3,6*n-1,6*n+1]
arr = [2,3]
user = int(input("请输入一个值，我将输出0-该值之内的所有素数(例1048576):"))
if(user>pow(5,13)):
    print("请输入一个在int范围内,且不是特别大的数(小于5^13=1,220,703,125)")
    user = int(input("请输入一个值，我将输出0-该值之内的所有素数(例1048576):"))
num = int(user/6)+3
f_arr(num)
#print(arr)           #查看arr生成情况

max = 0
for i in range(1,14):
    if(pow(5,i)>=user):
        max = i
        break
# 2、遍历 arr[]，从5开始，依次乘自身与比自身大的 arr[] 中的数
# 3、arr.remove() 删除得到的 arr[] 中的非质数
#print("max =",max)
brr = clear_arr(arr)

# 4、输出 brr[]
print(brr)
print("0 ~",user,"之间有:",len(brr),"个质数")

以上代码应该可进行优化，连续13个for循环有点丑，应该改可以写成一个函数，本人就不写了，读者有意可自行钻研修改

注：以上代码只适合 0 ~ 5^13 = 1,220,703,125 的范围内的质数的寻找，有符号 int 最大值为 2^31 = 2,147,483,648

7、公式法

无解(暂)


二、前面的C代码中用到的一些素数性质的python脚本验证(非严谨验证)

注：前面的C代码生成的1.txt文件直接copy进下方python代码中的数组即可直接操作质数

1、数以质数方式增长，查看质数增长情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
##!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import string

shuzu = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,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,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,
1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,
2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,
2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,
3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,
3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,
3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,
3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,
4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,
4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,
4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,
4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,
4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,
4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,
5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,
5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,
5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,
5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,
5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,
5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,
6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,
6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,
6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,
6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,
6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,
7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,
7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,
7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,
7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,
7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,
7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,
8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,
8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,
8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,
8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,
8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,
9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,
9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,
9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,
9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,
9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,
9901,9907,9923,9929,9931,9941,9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10093,10099,
10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193,10211,10223,10243,10247,10253,10259,10267,10271,
10273,10289,10301,10303,10313,10321,10331,10333,10337,10343,10357,10369,10391,10399,10427,10429,10433,10453,10457,10459,
10463,10477,10487,10499,10501,10513,10529,10531,10559,10567,10589,10597,10601,10607,10613,10627,10631,10639,10651,10657,
10663,10667,10687,10691,10709,10711,10723,10729,10733,10739,10753,10771,10781,10789,10799,10831,10837,10847,10853,10859,
10861,10867,10883,10889,10891,10903,10909,10937,10939,10949,10957,10973,10979,10987,10993,11003,11027,11047,11057,11059,
11069,11071,11083,11087,11093,11113,11117,11119,11131,11149,11159,11161,11171,11173,11177,11197,11213,11239,11243,11251,
11257,11261,11273,11279,11287,11299,11311,11317,11321,11329,11351,11353,11369,11383,11393,11399,11411,11423,11437,11443,
11447,11467,11471,11483,11489,11491,11497,11503,11519,11527,11549,11551,11579,11587,11593,11597,11617,11621,11633,11657,
11677,11681,11689,11699,11701,11717,11719,11731,11743,11777,11779,11783,11789,11801,11807,11813,11821,11827,11831,11833,
11839,11863,11867,11887,11897,11903,11909,11923,11927,11933,11939,11941,11953,11959,11969,11971,11981,11987,12007,12011,
12037,12041,12043,12049,12071,12073,12097,12101,12107,12109,12113,12119,12143,12149,12157,12161,12163,12197,12203,12211,
12227,12239,12241,12251,12253,12263,12269,12277,12281,12289,12301,12323,12329,12343,12347,12373,12377,12379,12391,12401,
12409,12413,12421,12433,12437,12451,12457,12473,12479,12487,12491,12497,12503,12511,12517,12527,12539,12541,12547,12553,
12569,12577,12583,12589,12601,12611,12613,12619,12637,12641,12647,12653,12659,12671,12689,12697,12703,12713,12721,12739,
12743,12757,12763,12781,12791,12799,12809,12821,12823,12829,12841,12853,12889,12893,12899,12907,12911,12917,12919,12923,
12941,12953,12959,12967,12973,12979,12983,13001,13003,13007,13009,13033,13037,13043,13049,13063,13093,13099,13103,13109,
13121,13127,13147,13151,13159,13163,13171,13177,13183,13187,13217,13219,13229,13241,13249,13259,13267,13291,13297,13309,
13313,13327,13331,13337,13339,13367,13381,13397,13399,13411,13417,13421,13441,13451,13457,13463,13469,13477,13487,13499,
13513,13523,13537,13553,13567,13577,13591,13597,13613,13619,13627,13633,13649,13669,13679,13681,13687,13691,13693,13697,
13709,13711,13721,13723,13729,13751,13757,13759,13763,13781,13789,13799,13807,13829,13831,13841,13859,13873,13877,13879,
13883,13901,13903,13907,13913,13921,13931,13933,13963,13967,13997,13999,14009,14011,14029,14033,14051,14057,14071,14081,
14083,14087,14107,14143,14149,14153,14159,14173,14177,14197,14207,14221,14243,14249,14251,14281,14293,14303,14321,14323,
14327,14341,14347,14369,14387,14389,14401,14407,14411,14419,14423,14431,14437,14447,14449,14461,14479,14489,14503,14519,
14533,14537,14543,14549,14551,14557,14561,14563,14591,14593,14621,14627,14629,14633,14639,14653,14657,14669,14683,14699,
14713,14717,14723,14731,14737,14741,14747,14753,14759,14767,14771,14779,14783,14797,14813,14821,14827,14831,14843,14851,
14867,14869,14879,14887,14891,14897,14923,14929,14939,14947,14951,14957,14969,14983,15013,15017,15031,15053,15061,15073,
15077,15083,15091,15101,15107,15121,15131,15137,15139,15149,15161,15173,15187,15193,15199,15217,15227,15233,15241,15259,
15263,15269,15271,15277,15287,15289,15299,15307,15313,15319,15329,15331,15349,15359,15361,15373,15377,15383,15391,15401,
15413,15427,15439,15443,15451,15461,15467,15473,15493,15497,15511,15527,15541,15551,15559,15569,15581,15583,15601,15607,
15619,15629,15641,15643,15647,15649,15661,15667,15671,15679,15683,15727,15731,15733,15737,15739,15749,15761,15767,15773,
15787,15791,15797,15803,15809,15817,15823,15859,15877,15881,15887,15889,15901,15907,15913,15919,15923,15937,15959,15971,
15973,15991,16001,16007,16033,16057,16061,16063,16067,16069,16073,16087,16091,16097,16103,16111,16127,16139,16141,16183,
16187,16189,16193,16217,16223,16229,16231,16249,16253,16267,16273,16301,16319,16333,16339,16349,16361,16363,16369,16381,
]

#print(len(shuzu))

for i in range(2,14):
    n=0
    m=pow(2,i-1)
    for j in shuzu:
        if(j < m):continue

        if(j >= m and j < pow(2,i)):
            #print(j)
            n+=1
        if(j>=pow(2,i)):break
    print("2 ^",i-1," ~ ","2 ^",i," 有",n," 个质数")

一些发现：随着正整数数量的指数倍生长，质数的数量其实也类似于指数倍生长

2、查看模n后，质数余数的分布：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
##!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import string

shuzu = [#数组同上，太多了，这里删除了，数组可由代码生成到txt再粘贴进来]

c = int(input("请输入模数:"))
#print("c=",c)
b = [[i,0]for i in range(0,c+1)]
for i in shuzu:
    a = i%c
    b[a][1] += 1

for i in range(0,c+1):
    if(b[i][1]!=0):
        print(b[i])

一些发现：

image-20230304043307987

1
#质数与数字6之间似乎有某种不可告人的秘密，一个质数模6的倍数得到的数一定是质数，1除外

得到的启发：

1
2
3
#我们是不是可以定义一个集合 arr = [2、3、6n-1、6n+1] ，由上面的推导可知所有质数都在此集合中
#那么我们是否能找到一种方式，准确而又简便地剔除掉 arr 中的非质数元素 ?
#该怎么剔除呢 ?

初步尝试：输出 [2,3,6n-1,6n+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>

int main()
{
    int a,b,c,num,i,j,k;
    
    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&num);
    a = num/3+4;           //加入2、3以及多一组6n-1、6n+1
    
    //--/linux gcc编译器不支持以下写法，本代码是在windows上运行的/--//
    int arr[a+100]={0};   //数组稍微开大，防止溢出
    
    arr[0] = 2;
    arr[1] = 3;
    for(i=2;i<=a;1){
        b = 6*(i-1)-1;
        c = b+2;
        if(b%6==1 || b%6==5){
            arr[i] = b;
            i++;
        }
        if(c%6==1 || c%6==5){
            arr[i] = c;
            i++;
        }
    }
    k=0;
    for(i=0;i<=a;i++){
        k++;
        printf("%d,",arr[i]);
        if(k%15==0)printf("\n");
    }
    printf("0~%d 中有 %d 个 [2,3,6n-1,6n+1] 数组数",num,k);
    //--/结果：0~16384 中有 5466 个 [2,3,6n-1,6n+1] 数组数/--//
    //--/0~16384中有1900个素数，还得通过筛选尽量使5466变成1900/--//
    return 0;
}

image-20230304114024665

第二次尝试：筛选 [2,3,6n-1,6n+1]，用于筛选的数可由上面的python代码进行查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>

int main()
{
    int a,b,c,num,i,j,k;
    
    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&num);
    a = num/3+4;           //加入2、3以及多一组6n-1、6n+1 
    
    //--/linux gcc编译器不支持以下写法，本代码是在windows上运行的/--//
    int arr[a+100]={0};    //数组稍微开大，防止溢出
    
    arr[0] = 2;
    arr[1] = 3;
    int x=2;
    for(i=2;i<=a && b<=num;i++){
        b = 6*(i-1)-1;
        c = b+2;
        //--/除2、3外，素数模10，末尾必是1、3、7、9/--//
        if(b%10==1 || b%10==3 || b%10==7 || b%10==9){    
            arr[x] = b;
            x++;
        }
        if(c%10==1 || c%10==3 || c%10==7 || c%10==9){
            arr[x] = c;
            x++;
        }
    }
    k=0;
    for(i=0;i<=a && arr[i]!=0;i++){
        k++;
        printf("%d,",arr[i]);
        if(k%15==0)printf("\n");
    }
    printf("0~%d 中有 %d 个 [2,3,6n-1,6n+1] 数组数",num,k);
    //--/结果：0~16384 中有 4371(得-1) 个 [2,3,6n-1,6n+1] 数/--//
    //--/0~16384中有1900个素数，还得通过筛选尽量使4371变成1900/--//
    //--/根据数字的生成性(个人看法)，继续筛下去没有意义/--//
    //--/在找出域中所有质数之前筛选只能无限接近但不能等于/--//
    //--/能找出来域中所有质数，筛选也就没有意义了/--//
    return 0;
}

收获：这条路或许行不通，还是得从别的角度探索质数的生长规律。

第三次尝试：加筛选条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>

int main()
{
    int a,b,c,num,i,j,k;
    
    printf("请输入想要查找的质数范围的最大数值(例:16384)：");
    scanf("%d",&num);
    a = num/3+4;           //加入2、3以及多一组6n-1、6n+1 
    
    //--/linux gcc编译器不支持以下写法，本代码是在windows上运行的/--//
    int arr[a+100]={0};    //数组稍微开大，防止溢出
    
    arr[0] = 2;
    arr[1] = 3;
    int x=2; 
    for(i=2;i<=a && b<=num;i++){
        b = 6*(i-1)-1;
        c = b+2;
    
        //--/除2、3外，素数模10，末尾必是1、3、7、9/--//
        if(b%10==1 || b%10==3 || b%10==7 || b%10==9){    
            if(b%20==1||b%20==3||b%20==7||b%20==9||b%20==11||b%20==13||b%20==17||b%20==19){
                arr[x] = b;
                x++;
            }
        }
        if(c%10==1 || c%10==3 || c%10==7 || c%10==9){
            if(c%20==1||c%20==3||c%20==7||c%20==9||c%20==11||c%20==13||c%20==17||c%20==19){
                arr[x] = c;
                x++;
            }    
        }
    }
    k=0;
    for(i=0;i<=a && arr[i]<=num+1;i++){
        k++;
        printf("%d,",arr[i]);
        if(k%15==0)printf("\n");
    }
    printf("0~%d 中有 %d 个 [2,3,6n-1,6n+1] 数组数",num,k);
    //--/结果：0~16384 中有 4370 个 [2,3,6n-1,6n+1] 数/--//
    //--/行不通，不试了/--//
    
    return 0;
}

三、素数的性质总结及其他

1、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 2 ^ 1  ~  2 ^ 2  有 2  个质数
# 2 ^ 2  ~  2 ^ 3  有 2  个质数
# 2 ^ 3  ~  2 ^ 4  有 2  个质数
# 2 ^ 4  ~  2 ^ 5  有 5  个质数
# 2 ^ 5  ~  2 ^ 6  有 7  个质数
# 2 ^ 6  ~  2 ^ 7  有 13  个质数
# 2 ^ 7  ~  2 ^ 8  有 23  个质数
# 2 ^ 8  ~  2 ^ 9  有 43  个质数
# 2 ^ 9  ~  2 ^ 10  有 75  个质数
# 2 ^ 10  ~  2 ^ 11  有 137  个质数
# 2 ^ 11  ~  2 ^ 12  有 255  个质数
# 2 ^ 12  ~  2 ^ 13  有 464  个质数
# 2 ^ 13  ~  2 ^ 14  有 872  个质数
# 2 ^ 14  ~  2 ^ 15  有 1612  个质数
# 2 ^ 15  ~  2 ^ 16  有 3030  个质数
# 2 ^ 16  ~  2 ^ 17  有 5709  个质数
# 2 ^ 17  ~  2 ^ 18  有 10749  个质数
# 2 ^ 18  ~  2 ^ 19  有 20390  个质数
# 2 ^ 19  ~  2 ^ 20  有 38635  个质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# 2   / 5  = 0.4
# 5   / 7  = 0.7142857...(142857为循环数)
# 7   / 13  = 0.538461...(153846为循环数)
# 13  / 23  = 0.5652173913043478260869...(5652173913043478260869为循环数)
# 23  / 43  = 0.534883720930232558139...(534883720930232558139为循环数)
# 43  / 75  = 0.573333333...(75是非质数，3为循环数)
# 43  / 137  = 0.31386861...(13138686为循环数) 
# 75  / 137  = 0.547445255...(47445255为循环数)
# 137 / 255  = 0.5372549019607843137(255是非质数，2549019607843137为循环数)
# 137 / 464  = 0.29525862068965517241379310344828...(464是偶数，win10自带计算器只能算到这一位，不知道是否存在循环) 
# 137 / 872  = 0.15711009174311926605504587155963...(872是偶数，win10自带计算器只能算到这一位，不知道是否存在循环)
# 137 / 1612 = 0.08498759305210918114143920595533...(1612是偶数，不知道是否存在循环)
# 137 / 3030 = 0.04521452...(3030是偶数，1452是循环数)
# 1612/ 3030 = 0.53201...(3201是循环数)
# 137 / 5709 = 0.02399719740760203187948852688737...(5709是非质数，不知道是否存在循环)

# 非质数貌似不太友好，下面列出一些质数相除结果

# 1
  # 182593 / 501191 = 0.36431819406174492359200384683683...(观测不出规律)
  # 862013 / 1041149 = 0.82794393501794651870193411317688...(观测不出规律)

# 50
  # 5437 / 9283 = 0.58569427986642249272864375740601...(观测不出规律)

# 200
  # 101 / 1259 = 0.08022239872915011914217633042097...(观测不出规律)

# 400
  # 47  / 211  = 0.22274881516587677725118483412322...(观测不出规律)
  # 613 / 659  = 0.93019726858877086494688922610015...(观测不出规律)
  # 59  / 1129 = 0.0522586359610274579273693534101...(观测不出规律)
    
# 1600
  # 211 / 229  = 0.92139737991266375545851528384279...(观测不出规律)

# 3200
  # 17  / 47   = 0.36170212765957446808510638297872...(观测不出规律)
  # 23  / 29   = 0.79310344827586206896551724137931...(观测不出规律)
  # 13  / 61   = 0.21311475409836065573770491803279...(观测不出规律)
  # 37  / 67   = 0.55223880597014925373134328358209...(观测不出规律)
  # 23  / 89   = 0.25842696629213483146067415730337...(观测不出规律)
 
# ??? 为什么之前还能找到许多较短的循环数，现在用两个质数相除就找不到了呢

# 手动寻找
  # 7 / 11 = 0.63636363636363636363636363636364...(计算器算的，末尾会进位，循环数63)
  # 7 / 17 = 0.41176470588235294117647058823529...(循环数4117647058823529)
  # 7 / 19 = 0.36842105263157894736842105263158...(循环数368421052631578947)
  # 7 / 23 = 0.30434782608695652173913043478261...(循环数3043478260869565217391)
  # 7 / 29 = 0.24137931034482758620689655172414...(循环数2413793103448275862068965517)
  # 7 / 31 = 0.22580645161290322580645161290323...(猜测循环数为225806451612903225806451612903)
  # 7 / 37 = 0.18918918918918918918918918918919...(循环数189)
    # 63/189 = 0.33333333333333333333333333333333.(循环数3)
  # 7 / 41 = 0.17073170731707317073170731707317...(循环数17073，最近的一个质数是17077，上一个质数是17053)
  # 7 / 43 = 0.16279069767441860465116279069767...(162790697674418604651)
  # 7 / 47 = 0.1489361702127659574468085106383....(观测不出规律)
  # 7 / 53 = 0.13207547169811320754716981132075...(1320754716981)
  # 7 / 59 = 0.11864406779661016949152542372881...(观测不出规律)
  # 7 / 61 = 0.11475409836065573770491803278689...(观测不出规律)
  # 7 / 71 = 0.09859154929577464788732394366197...(观测不出规律，开头985 [doge])
  # 7 / 73 = 0.09589041095890410958904109589041...(95890410)
  # 7 / 79 = 0.08860759493670886075949367088608...(8860759493670)
  # 7 / 83 = 0.08433734939759036144578313253012...(观测不出规律)
  # 7 / 89 = 0.07865168539325842696629213483146...(观测不出规律)
  # 7 / 97 = 0.07216494845360824742268041237113...(观测不出规律)
  # 7 / 101 = 0.06930693069306930693069306930693..(6930)
  # 7 / 103 = 0.06796116504854368932038834951456..(观测不出规律)
  # 7 / 107 = 0.0654205607476635514018691588785...(观测不出规律)
  # 7 / 109 = 0.06422018348623853211009174311927..(观测不出规律)
  # 7 / 113 = 0.06194690265486725663716814159292..(观测不出规律)
  # 7 / 127 = 0.05511811023622047244094488188976..(观测不出规律)
  # 7 / 131 = 0.05343511450381679389312977099237..(观测不出规律)
  # 7 / 137 = 0.05109489051094890510948905109489..(51094890)
  # 7 / 139 = 0.05035971223021582733812949640288..(观测不出规律)

  # 11 / 19 = 0.57894736842105263157894736842105..(210526315789473684)
  # ......
  # 7  / 19 = 0.36842105263157894736842105263158...(循环数368421052631578947)

启发：

1
2
3
# 1、 似乎(-1,0)∪(0,1)之间的小数可以由(-∞,+∞)的任意两整数两两相除得来(除数大于被除数)
# 2、 如果将(-1,0)∪(0,1)小数域看成是一个小小的原子，那么(-∞,+∞)就好比整个宇宙
# 3、 而将 1、去类比 2、就好像一个小小原子与整个宇宙之间都存在着某种联系，或者说一个原子就包含着一个宇宙

2、

1
2
3
4
1^1 = 1    个正方体： 2^3=8个顶点    12条边  6个面
3^3 = 27   个正方体： 4^3=64个顶点   (27*8=216)
5^3 = 125  个正方体： 6^3=216个顶点
......

image-20230305004247556

3、Tools

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
##!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import string

shuzu = []    #这里填入素数集 例：shuzu = [2,3,5,7,11,13,...,1048573,]

#print(len(shuzu))

''' ----------------------------------------------------------------------------
for i in range(2,21):
    n=0
    m=pow(2,i-1)
    for j in shuzu:
        if(j < m):continue

        if(j >= m and j < pow(2,i)):
            #print(j)
            n+=1
        if(j>=pow(2,i)):break
    print("2 ^",i-1," ~ ","2 ^",i," 有",n," 个质数")
'''



''' ----------------------------------------------------------------------------
c = int(input("请输入模数:"))
#print("c=",c)
b = [[i,0]for i in range(0,c+1)]
for i in shuzu:
    a = i%c
    b[a][1] += 1

for i in range(0,c+1):
    if(b[i][1]!=0):
        print(b[i])
'''



''' ----------------------------------------------------------------------------
arr = [2,3]
print("\n")
print("5 ^ 0 ~ 5 ^ 1 有 2 个质数")
print(arr)
for i in range(2,7):
    arr = []
    n=0
    m=pow(5,i-1)
    for j in shuzu:
        if(j < m):continue

        if(j >= m and j < pow(5,i)):
            #print(j)
            arr.append(j)
            n+=1
        if(j>=pow(5,i)):break
    print("\n")
    print("5 ^",i-1," ~ ","5 ^",i," 有",n," 个质数")
    print(arr)
'''

'''
for i in range(0,100):
    print("10000000 ÷",shuzu[i],"=",10000000/shuzu[i])
for i in range(0,100):
    print(shuzu[i],"÷",shuzu[i+1],"=",shuzu[i]/shuzu[i+1])
'''

''' ----------------------------------------------------------------------------
len = int(len(shuzu)/3200)  # 1600 400 200 50 1
print("len =",len)
num1 = random.randint(2,len)
num2 = random.randint(2,len)

while(num2==num1):num2 = random.randint(2,len)

if(num2>num1):
    num3 = shuzu[num1]/shuzu[num2]
    print("num1 =",shuzu[num1],"\nnum2 =",shuzu[num2],"\nnum1/num2 =",num3)
else:
    num3 = shuzu[num2]/shuzu[num1]
    print("num1 =",shuzu[num1],"\nnum2 =",shuzu[num2],"\nnum2/num1 =",num3)
'''

4、RSA

RSA加密中使用到的大质数并不是实实在在地算出了1024个bit位的质数，而是随机选中一个最高bit位为1的奇数，然后对这个数进行 素性检测 倘若这个数过了5-10轮素性检测，那么就用它作为RSA加密中的一个基本素数，所以通过这种方法得到的数可能不是素数(个人观点)

参考链接：RSA —— 经典的非对称加密算法 - 知乎 (zhihu.com)

参考链接：算法学习笔记(48): 米勒-拉宾素性检验 - 知乎 (zhihu.com)

参考链接：用于加密的超大素数是怎么得到的？ - 知乎 (zhihu.com)