● 1000000以内的素数(zz) - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: Version (为了你，为了我...), 信区: Program
标  题: 1000000以内的素数(zz)
发信站: 荔园晨风BBS站 (Sat Aug  9 13:37:14 2003), 转信

// Written in ANSI C++
// Celeron 1.1G Linux Gentoo 1.4下面用
// g++ -O3编译
// 用 time primes > /dev/null
// 测量时间为0.9s左右。
// 还有更快的算法么?
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

// type implementation
typedef unsigned long nature;
typedef std::vector<nature> natures;

// indirect comparison
struct indirect_cmp
        : std::binary_function<nature, nature, bool>
{
        indirect_cmp(const natures& ptr) : ptr_(ptr)
        {
        }

        bool operator() (nature n1, nature n2) const
        {
                return ptr_[n2] < ptr_[n1];

        }
        const natures & ptr_;
};

const unsigned UPPER_LIMIT = 1000000U;
const unsigned INIT_SIZE = 25U * 25U * 25U;

// This program prints all the primes less than 1000000.

int main()
{
        using namespace std;

        natures incrs, folds, index;
        indirect_cmp cmp(folds);

        incrs.reserve(INIT_SIZE);
        folds.reserve(INIT_SIZE);
        index.reserve(INIT_SIZE);

        incrs.push_back(3*2);
        folds.push_back(9);
        index.push_back(0);

        printf("2\n3\n");
        for(nature i = 5U; i < UPPER_LIMIT; i+= 2U) {
                if (folds[index[0]] == i)
                {

                        do {
                                pop_heap(index.begin(), index.end(), cmp);
                                nature last = *index.rbegin();
                                folds[last] += incrs[last];
                                push_heap(index.begin(), index.end(), cmp);
                        } while (folds[index[0]] == i);
                }
                else
                {
                        printf("%lu\n", i);
                        incrs.push_back(i*2);
                        folds.push_back(i*3);
                        index.push_back(index.size());
                        push_heap(index.begin(), index.end(), cmp);
                }

        }

        return 0;
}

--
                      *
          *                                  *
                          *             *
                      no more to say
                  ★     just wish you   ★
                            good luck

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.50]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店