同余筛法应用

小草

同余筛法应用

同余定理

若
a≡c1  modp1
a≡c2  modp2
a≡c3  modp3
...
a≡ck  modpk

则
a+hpk#≡c1  modp1
a+hpk#≡c2  modp2
a+hpk#≡c3  modp3
...
a+hpk#≡ck  modpk


若偶数A*
A*≡c1  modp1
A*≡c2  modp2
A*≡c3  modp3
...
A*≡ck  modpk

且
A*=q1+qt1
A*=q2+qt2
A*=q3+qt3
...
A*=qk+qtk

这时我们有A=A*+hpk#，我们就称A与A*同余.

这时我们有
A*+hpk#=q1+(qt1+hpk#)
A*+hpk#=q2+(qt2+hpk#)
A*+hpk#=q3+(qt3+hpk#)
...
A*+hpk#=qk+(qtk+hpk#)

这时
qt1+hpk#
qt2+hpk#
qt3+hpk#
...
qtk+hpk#
中已经筛去了p1,p2,...,pk的合数，它们的素因子除了pti│pk#的数一定大于pk,总的说来这些合数的占比是非常少的，我们可以通过取不同的A*,h和pk#来得到：
D(A)=D(A*)+新增.使得D(A*)>0.

设A*=p1+p2
这里D(A)=D(A*)是指D(A)中的p1=D(A*)中的p1，D(A)中的p2=D(A*)中的p2+hpk#.

方法简单，素数对越来越多.

小草

2=0
4=2+2=1
6=3+3=1

2+6=8
因为D(2)=0
我们取A*=6,h=1,pk#=2
6+2=8
∈6=3+5=1
新增=0
4+6=10
8+2=10
∈8=3+7=1
新增=5+5=1
6+6=12
10+2=12
∈10=【3+9】=5+7=1
新增=0

小草

8+6=14
∈8=3+11=1
新增=7+7=1
10+6=16
∈10=3+13=5+11=2
新增=0
12+6=18
∈12=5+13=1
新增=7+11=1


14+6=20
∈14=3+17=7+13=2
新增=0
16+6=22
∈16=3+19=5+17=2
新增=11+11=1
18+6=24
∈18=5+19=7+17=2
新增=11+13

小草

20+6=26
∈20=3+23=7+19=2
新增=13+13=1
22+6=28
∈22=【3+25】=5+23=11+17=2
新增=0
24+6=30
∈24=【5+25】=7+23=11+19=2
新增=13+17=1

小草

2+30=32
26+6=32
∈26=3+29=【7+25】=13+19=2
新增=0
4+30=34
28+6=34
28=5+29=11+23
∈28=5+29=11+23=2
新增=3+31=17+17=2
30+6=36
∈30=7+29-【11+25】=13+23=2
新增=5+31=17+19=2