美文网首页
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 素数 + 打表 + 尺取法

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