Sum of Consecutive Prime Numbers UVA - 1210——素数表+初级dp思想

逃离我推掉我的手 2022-06-14 04:49 115阅读 0赞

Think:  
1题意：输入正整数n(2 <= n <= 10000),求连续素数之和等于n的方案数  
2思路：  
1>筛法建立素数表+初级dp思想(从后往前规划得到当前素数可连续组合得到的数值)  
2>参考博客：[“素数表+区间滑动”][Link 1]，[“素数表+区间枚举”][Link 2]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int tp, link[10400], dp[10400];
    
    void Init_prime();
    void Init_dp();
    
    int main(){
        Init_prime();
        Init_dp();
        int n;
        while(scanf("%d", &n) && n){
            printf("%d\n", dp[n]);
        }
        return 0;
    }
    void Init_prime(){
        int v[10400];
        tp = 0;
        memset(v, 0, sizeof(v));
        v[1] = 1, v[2] = 0;
        for(int i = 2; i <= 10000; i++){
            if(!v[i]){
                link[tp++] = i;
                for(int j = i*2; j <= 10000; j += i){
                    v[j] = 1;
                }
            }
        }
    }
    void Init_dp(){
        memset(dp, 0, sizeof(dp));
        for(int i = tp-1; i >= 0; i--){
            int t = 0;
            for(int j = i; j >= 0; j--){
                if(t + link[j] <= 10000){
                    t += link[j];
                    dp[t] += 1;
                }
                else
                    break;
            }
        }
    }

[Link 1]: http://blog.csdn.net/u014435976/article/details/38580433
[Link 2]: http://blog.csdn.net/acvcla/article/details/45547427
[vjudge]: https://vjudge.net/problem/UVA-1210

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关 Problem 50 Consecutive prime sum （线性筛）

Consecutive prime sum Problem 50 The prime 41, can be written as the sum of six co

深藏阁楼爱情的钟/ 2022年07月15日 03:22/ 0 赞/ 124 阅读

相关 POJ2739 Sum of Consecutive Prime Numbers

题目大意：给出一个数n，判断n是否可以被连续质数的和表示，可以的话，输出可能的情况总数。输入以0结束。 include <iostream> usi

心已赠人/ 2022年07月11日 12:08/ 0 赞/ 132 阅读

相关 POJ 2739 Sum of Consecutive Prime Numbers

> Sum of Consecutive Prime Numbers > Time Limit: 1000MS Memory Limit: 65536K > Total

川长思鸟来/ 2022年06月16日 09:16/ 0 赞/ 89 阅读

相关 Sum of Consecutive Prime Numbers UVA - 1210——素数表+初级dp思想

Think: 1题意：输入正整数n(2 <= n <= 10000),求连续素数之和等于n的方案数 2思路： 1>筛法建立素数表+初级dp思想(从后往前规划得到当前

逃离我推掉我的手/ 2022年06月14日 04:49/ 0 赞/ 116 阅读

相关 Sum of Different Primes——素数表+dp

Think: 1题意：输入n(n <= 1120), k(k <= 14)，询问由k个不同素数相加得到n的方案数，\{2， 4\}，\{4， 2\}属于一种方案，输入0,

素颜马尾好姑娘i/ 2022年06月14日 04:40/ 0 赞/ 117 阅读

相关 Prime Gap UVA - 1644——筛法建素数表

Think: 1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作 2方

￡神魔★判官ぃ/ 2022年06月14日 04:39/ 0 赞/ 128 阅读

相关 UVA - 10924 - Prime Words (素数)

输入一个由大小写字母组成的字符串，每个字符代表着不同的数字，计算出这个字符串的数值，判断是否是素数；首先我们打个素数表；然后利用ascll码存入数组中，然后判断就o

r囧r小猫/ 2022年06月07日 00:23/ 0 赞/ 89 阅读

相关 UVA - 10789 - Prime Frequency（素数打表）

题意是给出0-9，A-Z，a-z，组成的字符串，如果字符的个数是素数就输出这个字符。例如ABCC中的C的个数是素数，那么输出C；首先素数打表，剩下的就是如何储存每个

浅浅的花香味﹌/ 2022年06月07日 00:21/ 0 赞/ 157 阅读

相关 Sum of Consecutive Prime Numbers

一些正整数能够表示为一个或多个连续素数的和。给定一个正整数，有多少个这样的表示？例如，整数53有两个表示5+7+11+13+17和53；整数20没有这样的表示。注意加法操

约定不等于承诺〃/ 2022年03月29日 12:58/ 0 赞/ 136 阅读

相关 POJ2739-Sum of Consecutive Prime Numbers

[http://poj.org/problem?id=2739][http_poj.org_problem_id_2739] 素数上限不大而且每次要算，就先离线预处理了，也水

川长思鸟来/ 2021年11月26日 13:18/ 0 赞/ 152 阅读