我对素数一无所知

前言

本来今天打比赛的时候，一心想要打出1e9范围内的素数表，直到后来用python打了出来。。。

pip install primesieve

1
2
3
4
5

from primesieve import *
ans = primes(1e9)
with open('data.txt', 'w') as f:
    for number in ans:
        f.write(str(number)+',')

1e9范围内有50847534个素数，符合\(\frac{n}{ln(n)}\)的规律。
打出来的素数表的txt文本大小有478Mb之大。我真是一个智障，还痴心想要把打的表粘上去。
明天给自己的数论加一点技能点。。。
一般的素数表打在1e5的范围之内，因为可以采用平方枚举的方法，超过1e5的质数(任意的数都可以拆成若干个质数的乘积)就要暴力的进行计算了。
学习如何减小筛选素数的范围，比如今天做的那个二分求等比数列的和的小技巧，其实还不是很懂。
1e9范围内的素数的最大的间隔为282

1
2
3
4
5
6
7
8

from primesieve import *
ans = primes(1e9)
tot = count_primes(1, 1e9)
print(tot)
interval = -1
for i in range(1, tot):
    interval = max(interval, ans[i]-ans[i-1])
print(interval)

所以昨天的B题倒着枚举就行了。。。菜醒

未解决的问题