一道相亲题

在微信上看到一条非常有意思的相亲图片

第一道题，707829217开方数以内的数，也就30000以内，暴力枚举进行素数检查就行。

附加题：

排列组合+递归分治

附加题程序：

def zuheshu(n, k):#Cnk
    fenzi = 1;
    fenmu = 1;
    for i in range(k):
        fenzi *= n-i;
        fenmu *= i+1;
    return fenzi/fenmu;
def ndigit_num3_p(n):#任意n位数所含的3的总数
    sum = 0;
    for i in range(n):
        k = i+1;
        sum += k * zuheshu(n,k) * pow(9, n-k)
    return sum
def ndigit_num3_q(n):#以3开头的任意n+1位数所含3的总数
    sum = 0;
    for i in range(n+1):
        k = i;
        sum += (k+1) * zuheshu(n,k) * pow(9,n-k)
    return sum;

def jiou_res(num):#0~num的任意数所含3的总数，
    if num < 3:
        return 0;
    if num < 10:
        return 1;
    strnum = str(num)
    head = int(strnum[0])
    n = len(strnum) - 1
    tail = int(strnum[1:])
    if head < 3:
        res = head*ndigit_num3_p(n) + jiou_res(tail)
    elif head == 3:
        res = head*ndigit_num3_p(n) + (tail+1) + jiou_res(tail)
    else:
        res = (head-1)*ndigit_num3_p(n) + ndigit_num3_q(n) + jiou_res(tail)
    return res;

def main_hzq():
    res = jiou_res(707829217) - jiou_res(70782921)*4 - jiou_res(70782920)
    print(res)

368247332