求200万以内质数的个数

qingyun

newkid ,OO 兄，你们真是太强了； 那就把一些常见的数论和概率论问题都让你们解决吧；
关键看你们有没有这么多时间研究，比如把几个最经典的问题用SQL接一下：
1.哥德巴赫猜想
  任意一个充分大的偶数=一个素数+另一个素数 (200万以内的)
2.四色问题
  就是地图上，有很多接壤的国家；只需要最少4种颜色就可以把这些国家区分下来；

〇〇

14年后写的还不如以前的
--duckdb
with
a as (select value from generate_series(3,1000,2)_(value)) --all odds divider
,t as(select * from a
except
select a.value*b.value from a,a b where a.value <=sqrt(1000) and b.value <=1000/3+1)
,a2 as(select value from generate_series(3,1000000,2)_(value)) --all odds
,t2 as(select * from a2
except
select a.value*b.value from a,a2 b where a.value <=sqrt(1000000) and b.value <=1000000/3+1)
select 2+sum(value) from t2;

37550402023
Run Time (s): real 7.116 user 25.537364 sys 1.700411

〇〇

27楼的duckdb语法改写，差了几万，不知问题出在哪
with t0 as
(select level*2+1 l from range(1,1+(sqrt(1000000)/2)::int) _(level)),
t1 as (select level*2+1 l from range(1,1+(sqrt(1000000)/3)::int) _(level))
,p1k as(select l from t0
except
select t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(1000000))
and t1.l<=t2.l and t1.l*t2.l<=1000000
)
,t as
(select level*6+1 l from range(1,1+(1000000/6)::int) _(level)
union all
select level*6+5 l from range(1,1+(1000000/6)::int) _(level)
)
,p2m as(select l from t
except
select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from p1k t1,t t2 where t1.l<=sqrt(1000000)
and t1.l<=t2.l and t1.l*t2.l<=1000000 and t2.l<=(1000000/19)
except
select level*5 from range(1,1+(1000000/5)::int) _(level)
except
select level*7+7 from range(1,1+(1000000/7)::int) _(level)
except
select level*11+11 from range(1,1+(1000000/11)::int) _(level)
except
select level*13+13 from range(1,1+(1000000/13)::int) _(level)
except
select level*17+17 from range(1,1+(1000000/17)::int) _(level)
)
select sum(l) from p2m;

37553402024

Run Time (s): real 0.200 user 0.343202 sys 0.296402


溢出了
D select * from t24 order by l desc limit 10;

1000007
1000003
1000001

〇〇

递归版本

with recursive a as(select value from generate_series(3,1000000,2)_(value))
,t as(select 3 lv, value from a
union all
select min(case when value>lv then value end) over(),t.value from t where (t.value<=lv or (t.value>lv and t.value % lv<>0)) and lv< sqrt(1000000) )
select 2+sum(value) from t where lv=(select max(lv)from t);

37550402023

Run Time (s): real 3.479 user 3.463222 sys 0.015600

newkid

你是想用筛法，但是中间数据太多了，都是垃圾。当N=两百万时ORACLE的递归WITH好几分钟都出不来。

with  a as(SELECT 2*ROWNUM+1 value FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1-1)
,t(lv,value)
as(select 3 lv, value from a
union all
select min(case when value>lv then value end) over(),t.value from t where (t.value<=lv or (t.value>lv and mod(t.value,lv)<>0)) and lv< sqrt(:n) )
select 2+sum(value) from t where lv=(select max(lv)from t);

〇〇

oracle没duckdb快，N=200w
142913828922

Run Time (s): real 10.451 user 9.843663 sys 0.608404

〇〇

看到一个快速筛算法 https://ask.csdn.net/questions/7850344


# 返回所有素数(小于n)的数量
n=int(input('请输入一个整数：'))
n -= 1
if n < 2:
    print(0)
r = int(n ** 0.5)
V = [n//d for d in range(1, r + 1)]
V += list(range(V[-1] - 1, 0, -1))            
S = {v: v - 1 for v in V}
#print(S)
for p in range(2, r + 1):
    if S[p] == S[p - 1]:
        continue
    p2 = p * p
    sp_1 = S[p - 1]
    for v in V:
        if v < p2:
            break
        S[v] -= S[v//p] - sp_1
print(S[n])


没懂

〇〇

这个欧拉筛好懂一些 https://www.cnblogs.com/Judge/p/11690114.html
def getPrime(n):
    v=[0 for i in range(n+3)]
    p=[]
    for i in range(2,n+1):
        if v[ i]==0:
            p.append(i)
#            print(i)
        for j in p:
            if i*j>n:
                break
            v[i*j]=1
            if i%j==0:
                break
    return p

其实也没少筛很多
如果把原始算法的偶数排除，就和它差不多

〇〇

sqlite版本 https://github.1git.de/PlummersSoftwareLLC/Primes/blob/drag-race/PrimeSQL/solution_1/sqlite_runner.py