美文网首页
poj2739 素数 + 打表 + 尺取法

poj2739 素数 + 打表 + 尺取法

作者: 暖昼氤氲 | 来源:发表于2019-11-20 15:15 被阅读0次
 /*
Time:2019.11.15
Author: Goven
type:素数 + (艾氏筛法打表)打表 + 尺取法 
err:runtime err
ref:https://blog.csdn.net/cc_1012/article/details/88978103
*/
//暴力+runtime err 
#include<iostream>
#include<cmath>
using namespace std;

bool a[1005];

int main()
{
    for (int i = 2; i < 10001; i++) a[i] = true;
    for (int i = 2; i < 10001; i++) {
        if (a[i]) {
            for (int j = i + 1; j < 10001; j++) {
                if (j % i == 0) {
                    a[j] = false;
                }
            }   
        }
    }   
//  for (int i = 3; i < 10001; i++) {
//      a[i] = true;
//      for (int j = 2; j <= sqrt((double)i); j++) {
//          if (i % j == 0) {
//              a[i] = false;
//              break;
//          }
//      }
//  }
    
    int n, c, sum;
    while (cin >> n && n) {
        c = 0;
        for (int i = n; i >= 2; i--) {
            if (a[i]) {
                sum = 0;
                for (int j = i; j >= 2 && sum < n; j--) {
                    if (a[j]) {
                        sum += j;
                    }
                }
                if (sum == n) c++;  
            }
        }
        cout << c << endl;
    } 
    return 0;
}
//暴力+打表(正确版)
//ref:https://www.jianshu.com/p/09c7c3b48c10 
#include<iostream>
#include<cmath>
using namespace std;

bool a[10005];
int b[10005];
int cnt;

int main()
{
    for (int i = 2; i < 10001; i++) a[i] = true;
    for (int i = 2; i < 10001; i++) {
        if (a[i]) {
            b[cnt++] = i; 
            for (int j = i + i; j < 10001; j += i) {
                a[j] = false;
            }   
        }
    }   
    
    int n, c, sum;
    while (cin >> n && n) {
        c = 0;
        for (int i = 0; i < cnt; i++) {
            sum = b[i];
            int j = i + 1;
            while (sum < n && j < cnt) sum += b[j++];
            if (sum == n) c++;
        }
        cout << c << endl;
    } 
    return 0;
}
// 尺取法 核心算法O(n)
//ref:https://blog.csdn.net/cc_1012/article/details/88978103 
#include<iostream>
#include<cmath>
using namespace std;

bool a[10005];
int b[10005];
int cnt;

int main()
{
    for (int i = 2; i < 10001; i++) a[i] = true;
    for (int i = 2; i < 10001; i++) {
        if (a[i]) {
            b[cnt++] = i; 
            for (int j = i + i; j < 10001; j += i) {
                a[j] = false;
            }   
        }
    }   
    
    int n, c, sum, s, f;
    while (cin >> n && n) {
        s = f = sum = c = 0;
        while (true) {
            if (sum == n) c++;
            if (sum > n) sum -= b[s++];
            else {
                if (b[f] <= n) sum += b[f++]; 
                else break;
            }
        }
        cout << c << endl;
    } 
    return 0;
}

相关文章

  • poj2739 素数 + 打表 + 尺取法

  • 素数打表

  • hw4 注意事项 2021-03-26

    计算素数的题目不要打表(去网上抄1000以内的素数表),打表没有成绩,但是现实中是一种解决问题的办法。 打印乘法表...

  • 尺取法

    尺取法 尺取法核心思路 尺取法其实也是一种模拟,是解决寻找区间和问题的一种方法。 假如有这么一个问题:给你一些数,...

  • 尺取法

    尺取法是比赛中一个很有意思的技巧。尺取法一般要保证数列的单调性才能使用。 (POJ - 2566)Bound Fo...

  • (ACM)美素数(打表)

    一个十进制数,如果是素数,而且它的各位数字和也是素数,则称之为“美素数”,如29,本身是素数,而且2+9 = 11...

  • 素数练习题

    UVA 10375 UVA 10791 UVA10375 Choose and divide 题解 先素数打表,然...

  • poj3292 素数打表

    正确版 错误版-超时:

  • 尺取法(双指针)

    尺取法,顾名思义,就是用一把尺子,不断向右移动,在移动过程中维护某一性质并更新答案的方法,这种方法一般用来求满足某...

  • 尺取法 | 习题集

    写在前面 下面整理了五道关于尺取法的习题,通过题目进一步理解尺取法这一技巧。 POJ 3061——Subseque...

网友评论

      本文标题:poj2739 素数 + 打表 + 尺取法

      本文链接:https://www.haomeiwen.com/subject/dlmoictx.html