将一个数分解成多个素数和的方法数

简介:

题目描述:哥德巴赫猜想认为任一大于2的偶数,都可表示成两个素数之和,比如

6 = 2+2+2

6 = 3+3

10 = 2+2+2+2+2

10 = 2+2+3+3

10 = 2+3+5

10 = 3+7

像3+7与7+3只有顺序不一样的认为是一种方式

问:给定一个10000以内的偶数,将它表示为素数的和有几种方式?(结果对10^9+7取模)

 

分析:相当于求以质数为物品体积,背包容量为10000的,可以重复选择的背包,设p[i]是第i个质数,dp[i][n]表示把正整

数n拆分为不大于p[i]的若干质数和的方案数,则有dp[i][n]=dp[i-1][n]+dp[i][n-p[i]]

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 10005;
const LL MOD = 1000000007;

bool prime[N];
int p[N];
int k;

vector<LL> v1;
vector<LL> v2;
vector<LL> *p1;
vector<LL> *p2;

void isprime()
{
    k = 0;
    int i,j;
    memset(prime,true,sizeof(prime));
    for(i=2;i<N;i++)
    {
        if(prime[i])
        {
            p[k++] = i;
            for(j=i+i;j<N;j+=i)
            {
                prime[j] = false;
            }
        }
    }
}

void Work()
{
    p1 = &v1;
    p2 = &v2;
    for(int i=0;i<N;i++)
    {
        if(i&1) p1->push_back(0);
        else    p1->push_back(1);
    }
    for(int i=1;i<k;i++)
    {
        p2->clear();
        for(int j=0;j<N;j++)
        {
            if(j < p[i]) p2->push_back((*p1)[j]%MOD);
            else         p2->push_back(((*p1)[j]%MOD + (*p2)[j-p[i]]%MOD)%MOD);
        }
        vector<LL> *tmp;
        tmp = p2;
        p2 = p1;
        p1 = tmp;
    }
}

int main()
{
    int n;
    isprime();
    Work();
    while(cin>>n)
    {
        cout<<(*p1)[n]<<endl;
    }
    return 0;
}


目录
相关文章
|
6月前
|
算法
给定两个数,求这两个数的最大公约数
给定两个数,求这两个数的最大公约数
|
6月前
|
人工智能 Java C++
计算逆序对数
计算逆序对数
39 0
|
20天前
计算一个数为两个素数之和
【10月更文挑战第26天】计算一个数为两个素数之和。
21 9
|
22天前
两数之间的 Armstrong 数
【10月更文挑战第24天】两数之间的 Armstrong 数。
13 4
|
6月前
|
Python
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
355 1
|
6月前
|
算法 C语言
求解亲密数代码剖析
求解亲密数代码剖析
|
6月前
求十个数的乘积
求十个数的乘积
33 0
判断10-105之间有多少个素数,并输出所有素数。【素数又称为质数,定义为在大于1的 自然数中,除了1和它本身以外不再有其他因数的数
判断10-105之间有多少个素数,并输出所有素数。【素数又称为质数,定义为在大于1的 自然数中,除了1和它本身以外不再有其他因数的数
103 0
|
C++
数的分解
把 2019分解成 3个各不相同的正整数之和,并且要求每个正整数都不包含数字2和4,一共有多少种不同的分解方法?
80 0
给你一组数,求出其中两两最大公约数中最大的值
给你一组数,求出其中两两最大公约数中最大的值
65 0